CISC 3130
Data Structures
Associative Implementation Containers — I

Overview

Using a array list in which we maintain the elements in sorted order allows us to use a binary search for our lookup, which is logarithmic (O(log n)); adding elements, however, to such a sorted vector would involve a linear (O(n)) operation (the new element would have to be inserted at it proper position to maintain sortedness and the rest of the vector to its right slid over one position. The insertion of the n elements (assuming they arrived in random order) would thus be of quadratic cost.

What is needed are lookup AND insertion operations that are both O(log n) or better. There are two basic structures that provide us with such performance: trees (logarithmic), and hash tables (constant if done right).

Binary Trees

Terminology

• branches
• external(leaf)/internal node

  

• parent/child
• All nodes have a single parent, except for the root
• siblings
• ancestor/descendant

  

• subtree

  

• binary tree: 0, 1, or 2 two children for any node
  • empty tree is a binary tree
  • node with left and right children that are binary trees (recursive definition)

  

• path: sequence of branches from root to node
• level of a node: length of path from root to node
• depth of tree: maximum level of any node

Recursive Nature of Binary Tree

• Trees are recursive structures-- the children of a tree are themselves (sub)trees
• This property proves crucial when processing a tree

Binary Tree Nodes - Nodes

• Data and two links-- left and right
• Essentially the same as doubly linked nodes

class Node<E> {
	Node(Node<E>, E data, Node<E> right) {
		this.data = data;
		this.left = left;
		this.right = right;
	}
	private E data;
	private Node≤E> left, right;
}

Binary Tree

class BinaryTree {
	…
	Node<E> root;
}

Operations on a Binary Tree

• addRoot(data) - creates a single node (root-only) binary tree

  void addRoot(E data) {root = new Node(data);}
  		

• addLeft(data, node) - adds data as left child of node (only if no left child already)

  void addLeft(E data, Node node) {
  	if (node == null) throw new CollectionException("tree", "addLeft", "Non-existent node");
  	if (node.left != null) throw new CollectionException("binary tree", "addLeft", "node already has left child");
  	var newNode = new Node(data);
  	node.left = newNode;
  }
  		

• addRight(data, node) - adds data as right child of node (only if no right child already)

  void addRight(E data, Node node) {
  	if (node == null) throw new CollectionException("tree", "addRight", "Non-existent node");
  	if (node.right != null) throw new CollectionException("binary tree", "addRight", "node already has right child");
  	var newNode = new Node(data);
  	node.right = newNode;
  }
  		

• Traversals
  • Need to process the root and the two subtrees (recursive)
    • Processing can be printing, acquiring node's data or some modification to node
    • In the following code we'll present to illustrate traversal, we're going to restrict ourselves to printing
  • Usually left before right
  • That leaves us with choice of when to process root
  • Three choices:
    • preorder - visit root, traverse left, traverse right

      void prePrint(Node<E> root) {
      	if (root == null) return; 
      		System.out.println(root.data)
      		prePrint(root.left)
      		prePrint(root.right)
      }
      						

    • inorder - traverse left, visit root, traverse right

      void inPrint(Node<E> root) {
      	if (root == null) return; 
      		inPrint(root.left)
      		System.out.println(root.dataa)
      		inPrint(root.right)
      }
      						

    • postorder - traverse left, traverse right, visit root

      void postPrint(Node<E> root) {
      	if (root == null) return; 
      		postPrint(root.left)
      		postPrint(root.right)
      		System.out.println(root.data)
      }
      						

    • level-order - fully visit each level before going next level down
      • Use queue to hold onto nodes to be processed

Some Useful Algorithms

• Besides being useful, gives practice in working with the recursive structure of the tree

Node Count

#nodes in a tree =

• 0 if tree is empty (root is null)
• #nodes in left subtree + #nodes in right subtree + 1 (for the root)

int nodeCount(Node<E> root) {
	if (root == null) return 0;
	return nodeCount(root.left) + nodeCount(root.right) + 1
}
		

Leaf Count

#leaves in a tree =

• 0 if tree is empty (root is null)
• 1 if root is a leaf (no children)
• #leaves in left subtree + #leaves in right subtree if root is not leaf

int leafCount(Node<E> root) {
	if (root == null) return 0;
	if (root.left == null && root.right == null) return 1;
	return leafCount(root.left) + leafCount(root.right);
}

Depth of a Tree

• Recall depth of a tree is maximum level (path from root to any node)
• Only have to bother with leaf paths (Why?)

• 0 if tree is empty (root is null)
• 1 + max(depth of left subtree), depth of right subtree)

int depth(Node<E> root) {
	if (root == null) return 0
	return max(depth(root.left), depth(root.right)) + 1
}

Finding a Value in the Tree

value is there if

• it's in the root, or
• it can be found in the left subtree, or
• it can be found in the right

boolean contains(Node<E> root, E data) {
	if (root == null) return false
	if (data == root.data) return true
	return contains(root.left, data) || contains(root.right, data)
}

• Note the use of the short-circuiting operator ||
• Still might have to search whole tree; i.e., this is an O(n) operation

Finding the Maximum Value in the Tree

Maximum value of a (sub)tree is the maximum of the root's value and the maximum values of the left and right subtrees

int max(Node<E> root) {
	if (root == null) return 0 	// a 'cheat'
	return Math.max(root.data, max(root.left), max(root.right))
}
		

• What if the tree is empty? (that's why the 'cheat' is a cheat)
• the right way to do it is with a wrapper that first checks whether the tree is empty, and then invokes the recursive method

int max(Node<E> root) {		// a delegator of sorts
	if (root == null) throw new Exception("can't take max of empty tree");
	return max2(root);
}

int max2(Node<E> root) {		// private
	int result = root.data;
	if (root.left != null) result = max(result, max2(root.left);
	if (root.right != null) result = max(result, max2(root.right);
	return result;
}
		

Applications of Binary Trees

• Expression Trees
• Decision Trees
  • Guess the … game

General Trees

class GenTreeNode<E> {
	E data;
	ArrayList<GenTreeNode<E>> children;
}

• Games Trees

Binary Search Tree (BST) — An O(log n) Implementation of Searching

• Maintains a binary tree with the following property
  • The values in the left subtree of each node in a BST is less than the value at the node
  • The values in the right subtree of each node in a BST is greater than the value at the node
• Immediate consequence
  • Our contains algorith of the binary tree can be replaced with one that needs only look in either left or right subtree-- not both
  • Cuts our work in half (hopefully)
    • That's what produces the log (as opposed to n cost for searching)
• Again, it's the binary search tree that imposes this property, the binary tree is only providing the operations that we presented earlier
• Performing an inorder traversal of a binary search tree visits the nodes in their sorted order

Finding a Value in the BST

value is there if

• it's in the root, or
• it's less than the value in the root and it can be found in the left subtree, or
• it's greater than the value in the root and it can be found in the right subtree

bool contains(Node<E> root, E data) const {
        if (root == null) return false;
        if (data == root.data) return true;
        if (data.compareTo(root.data) < 0) return contains(root.left, data);
        return contains(root.right, data);
}
		

Implementation

class BinarySearchTree {
	…
private:
	BinaryTree binaryTree;
};

• BinarySearchTree can use the BinaryTree's operations (e.g. addLeft) to maintain the 'ordering' structure

Operations on a Binary Search Tree

• Search
  • Presented it above
• Insertion

  void add(E data) { 
  	Node<E> p = root, q = null;
  	while (p != null) {
  		q = p;
  		if (p.data.equals(data))
  			return;
  		else if (p.data.compareTo(data) < 0)
  			p = p.left;
  		else
  			p = p.right;
  	}
  	if (q == null) 
  		binaryTreetree.addRoot(data);
  	else if (q.data.compareTo(data) < 0)
  		binaryTree.addLeft(q, data);
  	else
  		binaryTree.addRight(q, data);
  }
  		

  or

  // Recursively
  
  void add(E data) {
  	if (binaryTree.root == null) 
  		binaryTree.addRoot(data);
  	else 
  		add(binaryTree.root, data);
  }   
  
  private void add(Node root, E data) {
  	if (data.equals(root.data)) return;
  	if (data.compareTo(root.data) < 0) {
  		if (root.left == null)
  			binaryTree.addLeft(data, root);
  		else 
  			add(root.left, data);
  	}   
  	else {
  		if (root.right == null)
  			binaryTree.addRight(data, root);
  		else 
  			add(root.right, data);
  	}   
  }   
  		

  or

  // Directly manipulating the underlying nodes (i.e., no composition)
  
  void add(E data) { 
  	Node<E> p = root, q = 0;
  	while (p != null) {
  		q = p;
  		if (p.data.equals(data))
  			return;
  		else if (p.data < data)
  			p = p.left;
  		else
  			p = p.right;
  	if (q == null)
  		root = new Node<E>(data);
  	if (q.data.compareTo(data) < 0)
  		insertLeft(q, data);
  	else
  		insertRight(q, data);
  }
  		

Heaps

• Full binary tree All nodes are either leaves or have two children
• Complete binary tree All levels are filled except lowest one, and in the lowest level, all nodes are as far to the left as possible
• Heap Complete binary tree in which every parent node is greater in value than either child

  

• Can be represented by a array/vector (with root a v[0])
• explicit references are replaced by implicits:
  • leftChild(i) → (2 * i) + 1
  • rightChild(i) → (2 * i) + 2
  • parent(i) → (i - 1) / 2
• logarithmic (O(logn)) lookup, insertion, and adjustment
• Implementation structure of a priority queue
  • We'll see this in more detail when we look at heapsort

Code related to this lecture