Advanced Tree Concepts
Binary search trees, in general, improve the runtime complexity of other ADTs
O(logN) Searching, for example
We can improve things even further by keeping track of more information in the tree
We can store backtracking information to produce iterative solutions, reducing the memory requirements of recursive solutions
Threading
General idea:
During insert, if there is no RIGHT child, then store a link to the next node to search, and set a mark saying you are doing this
search goes along normally, then follows the RIGHT child link if the marker says to do so
p. 451-453
Heaps
If we impose still more restrictions on binary trees, we can increase the efficiency even more
T is a Complete Binary Tree of Depth K iff each vertex at level K is a leaf, and all other vertices have exactly two children
T is an Almost Complete Binary Tree of Depth K iff it is either complete, or some right-most vertices at level K-1 are leaves
(Almost) Complete Binary Trees
Heap Properties
Unlike BSTs, heaps are sorted with greater values higher in the tree
For each node n in a heap H, n > n.left and n > n.right
There is no requirement that n.left > n.right
Heap Implementaion
The nice thing about heaps is that there is a straightforward implementation using arrays
The root is at position 1
Root’s children are at positions 2 & 3
Root’s grandchildren are at positions 4, 5, 6, & 7
Heap Implementation (cont.)
We can easily calculate:
Parent = Current / 2 (integers!)
LeftChild = Current * 2
RightChild = ( Current * 2 ) + 1
Heap Examples
How do the arrays look?
Operations on Heaps
An Almost Heap is a heap that fails to be a heap only because the value at the root may be smaller than one or both of its children
Adding to a Heap
Add the new node as the next child
Simply put it at the end of the array!
In order to preserve the greater-than ordering of the heap, “bubble” the node up until it satisfies the constraint
Bubbling means exchanging it with its parent
What does the exchange operation cost?
Heap Examples
Heap Examples (cont.)
Heap Examples (cont.)
Storage Options
Say you wanted to implement a spell-checker
You could store all the words:
in an array
in an ordered list
in a binary tree
something else?
What are the problems with these?
Digital Trees
Instead of storing the words explicitly, we can store them in a tree where each node is a letter
Each path through the tree represents a different word
Searching for a given word only requires a tree traversal from the root
Digital Trees (cont.)
Digital Tree Implementation
As a first approach, we could implement each node in the tree as an array of 27 elements (26 letters plus the ‘#’ marker)
Digital Tree Implementation (cont.)
This is not very space efficient
The arrays will mostly be sparse
Could use Left-Child/Right-Sibling Implementation
Balancing Trees
AVL Algorithm
Recall that a balanced tree is a tree such that for each node, the height of the left child is the same as the height of the right child +/-1
Notice that adding a node to a balanced tree results in a tree that is either:
Still balanced, or
has a node whose heights differ by at most 2
Balancing Trees (cont.)
Since an “unbalanced” tree can be off by at most 1 (2 really), we can balance it by rearranging that particular subtree
There is no need to rearrange the whole tree!
The AVL Algorithm applies “Right-Rotation” and/or “Left/Right Rotation” to balance a subtree after insertion
AVL Algorithm
PROCEDURE Rotate_R( T : IN OUT Tree ) IS
  Temp : Tree := T.Right;
BEGIN
  T.Right := Temp.Left;
  Temp.Left := T;
  T.Height :=
           Max(T.Right.Height,T.Left.Height)+1;
  Temp.Height := Max(Temp.Right.Height,
                     T.Height)+1;
  T := Temp;
END Rotate_R;
AVL Algorithm (cont.)
AVL Algorithm (cont.)