Home/Syllabus

Schedule/Notes

Topics

Trees

Where do you see "trees"? Binary Trees Terminology: nodes; parent; children; edge; path

Side note: why trees? Because arrays and linked lists don't provide both fast... Array Linked List Sorted Array search O(n) O(n) O(log n) insert O(1) (add to the end of the list) O(1) (add to the end of the list) O(n) ...and trees can provide both at O(log n)

Given a tree, the depth of a node M in the tree is the length of the path from the root of the tree to M. All nodes of depth d are at level d in the tree.

The height of a tree is one more than the depth of the deepest node in the tree.

Figure 1: A binary tree with 6 nodes.
Node A is the root, which has two children, B and C.
Nodes B and D together form a subtree.
The height of this tree is 3.
D, E and F make up level 2 of the tree (with depth of 2); they are leaves (leaf nodes that have no children, or two empty children).

Full vs Complete Binary Trees

• Full binary trees: Each node in a full binary tree is either an internal node with two non-empty children, or a leaf. The Huffman coding tree is an example of a full binary tree.
  
• In a complete binary tree, all levels except possibly level $d - 1$ are completely full (this is a consequence of how the tree is built — by levels from left to right). The heap data structure is an example of a complete binary tree.
  
  The complete binary tree (B) is not full. Why?

• The full binary tree theorem.

  Premise: binary tree implementations might require:
  • some amount of space for internal nodes (to provide structure to the tree)
  • and a different amount for leaf nodes (for storing the actual data),
  so it is important to know the minimum and maximum fraction of the nodes that are leaves in a tree containing $n$ internal nodes.
  
  The full binary theorem says that:

  the number of leaves in a non-empty full binary tree is one more than the number of internal nodes.

  A simple extension of the full binary theroem tells us how many empty subtrees there are in any binary tree:

  the number of empty subtrees in a non-empty binary binary tree is one more than the number of nodes in the tree.

How is the data stored in a tree?

• All nodes; leaf nodes only; the paths store the data (e.g, suffix tree).
  
• Node implementation (ADT; a Pointer-based Binary Node Class)
• Space requirements: the actual data plus overhead (space necessary for maintaining the data structure)

Array Implementation for Complete Binary Trees

Complete binary trees have all levels except the bottom filled out completely, and the bottom level has all of its nodes filled in from left to right. So a complete binary tree with n nodes only has one shape. Complete binary trees (including heaps) can be implemented using arrays, as simple formulas can be used for computing the array index for each relative of a node $r$ from $r's$ index as follows.

• Parent$(r) = \lfloor (r-1)/2 \rfloor$ if $r \ne 0$
• Left child$(r) = 2r + 1$ if $2r + 1 < n$
• Right child$(r) = 2r + 2$ if $2r + 2 < n$
• Left sibling$(r) = r - 1$ if $r$ is even
• Right sibling$(r) = r + 1$ if $r$ is odd and $r+1 < n$

Binary Tree Traversals (Chapter 5.2)

Given a binary tree,

• Any process for visiting all of the nodes in some order is called a traversal.
• Any traversal that lists every node in the tree exactly once is called an enumeration of the tree's node.
• Three common tree traversals:
  
  • inorder: left, root, right
    
  • preorder: root, left, right
    
  • postorder: left, right, root
    
• Example: Figure 1
  • inorder: BDAECF
  • preorder: ABDCEF
  • postorder: DBEFCA
• Time complexity: $\Theta(n)$

Binary Search Trees (BST)

• Binary Search Tree Property: All nodes stored in the left subtree of a node whose key value is K have key values less than K. In other words, all nodes stored in the right subtree of a node whose key value is K have key values greater than or equal to K.
  
• A BST is a binary tree that conforms to the binary search tree property.
• Search/insert/delete (using recursions) (Chapter 5.4)

  private E findNode(BSTNode node, K k) {
  	if(node == null) return null;
  	if(node.getKey().compareTo(k) > 0) return findNode(node.getLeft(), k);
  	else if(node.getKey().compareTo(k) == 0) return node.element();	
  	else return findNode(node.getRight(), k);
  }
  

• The shape of a BST depends on the order in which elements are inserted
  Order 1: 37 24 42 7 2 40 42 32 120
  Order 2: 120 42 42 7 2 32 37 24 40
• See an implementation (Binary Node ADT | Binary Node Class | BST Class)
  Note the remove function is a little trickier to implement, as the binary search tree property needs to be maintained!
• Time complexity
  search/insertion: $\Theta(logn)$ (average case), $\Theta(n)$ (worst case) (why?)
  building the tree: $\Theta(nlogn)$ (average case), $\Theta(n^2)$ (worst case)

Recursion

• The most common application of recursion is in mathematics and CS, where a function being defined is applied within its own definition.
  E.g., Fibonacci sequence is a classic example of recursion: Fib(0)=0, Fib(1)=1, and for n > 1, Fib(n)=Fib(n-1) + Fib(n-2)
• Naturally, if a data structure is defined recursively, it may be processed by a recursive function.
  E.g., findNode() function above

Heaps

Priority Queues

Huffman Coding Trees