Those are upper bound numbers which hold when a tree is fully expanded (i.e., a tree of depth d is complete and all nodes at depth 0 through d-1 have two children).
e.g. floor(lg31) = 4
class BinaryNode { // constructors BinaryNode( Comparable o ) { element = o; } BinaryNode( Comparable o, BinaryNode lt, BinaryNode rt ) { element = o; left = lt; right = rt; }// fields Comparable element; BinaryNode left; BinaryNode right; }
BinaryNode root; // start from an empty tree
A / \ B F \ / C G / \ D E
There are three different orders to visit nodes:
- Preorder -- 1) visit current node, 2) go left, then 3) go right
- Inorder -- 1) go left, 2) visit current node, then 3) go right
- Postorder -- 1) go left, 2) go right, then 3) visit current node
Preorder: A B C D E F G Inorder: B D C E A G F Postorder: D E C B G F A
void inorder(BinaryNode node) { if (node != null) { inorder(node.left); // go left first -- recursive call System.out.println(node.element); // then visit (print the node data) inorder(node.right); // and then go right -- recursive call } }
int SizeOfTree(BinaryNode n) { if (n == null) return 0; else return (1 + SizeOfTree(n.left) + SizeOfTree(n.right)); }
int TreeHeight(BinaryNode n) { if (n == null) return -1; else return (1 + Max(TreeHeight(n.left), TreeHeight(n.right))); }
Notice the tree respects operator precedence between * and -.
NOTE: If the expression was 3 * (5 - 2), the tree above is not correct -- The correct tree is different.
Preorder: - * 3 5 2 Inorder: 3 * 5 - 2 Postorder: 3 5 * 2 -
20 20 / \ / \ 12 31 12 31 / \ / \ => after / \ / \ 9 18 25 41 inserting 30 9 18 25 41 / / \ / \ / \ 15 35 60 15 30 35 60 \ \ 40 40
1) insert 30 2) insert 2 3) insert 42 4) insert 15 30 30 30 30 / / \ / \ 2 2 42 2 42 \ 15
However, if the same values are inserted in a different order: 2, 15, 30, 42
1) insert 2 2) insert 15 3) insert 30 4) insert 42 2 2 2 2 \ \ \ 15 15 15 \ \ 30 30 \ 42
Thus, depending on the order of insertion, a sequence of insertions may yield a degenerate tree.
Case 1: a leaf node is deleted
10 10 / \ / \ 5 15 => after 5 15 / \ / deleting 6 / / 3 6 12 3 12
Case 2: an internal node with one child is deleted
10 10 / \ / \ 5 15 => after 5 12 / \ / deleting 15 / \ / \ 3 6 12 3 6 11 13 / \ 11 13
10 / \ 5 15 => after / \ \ deleting 15 3 6 20 / \ 17 23
Case 3: an internal node with two children is deleted
Example: delete 31
20 / \ 12 31 / \ / \ => after 9 18 25 41 deleting 31 / / \ 15 35 60 \ 40
NOTE: The other way is also possible, that is, to replace data with the largest data in the left subtree.
public class BinarySearchTree { public BinarySearchTree( ) { root = null; } /** ** public methods -- most of them call their respective ** private methods immediately **/ public void insert( Comparable x ) { root = insert( x, root ); } public void remove( Comparable x ) { root = remove( x, root ); } public Comparable findMin( ) { return elementAt( findMin( root ) ); } public Comparable findMax( ) { return elementAt( findMax( root ) ); } public Comparable find( Comparable x ) { return elementAt( find( x, root ) ); } /** ** Internal (private) methods **/ private Comparable elementAt( BinaryNode t ) { return t == null ? null : t.element; } private BinaryNode insert( Comparable x, BinaryNode t ) { if( t == null ) t = new BinaryNode( x, null, null ); else if( x.compareTo( t.element ) < 0 ) t.left = insert( x, t.left ); // left child re-assigned else if( x.compareTo( t.element ) > 0 ) t.right = insert( x, t.right ); // right child re-assigned else ; // Duplicate (x exists already); do nothing return t; // Returns the reference to the current node. }
private BinaryNode remove( Comparable x, BinaryNode t ) { if( t == null ) return t; // Item not found; do nothing if( x.compareTo( t.element ) < 0 ) t.left = remove( x, t.left ); // left child re-assigned else if( x.compareTo( t.element ) > 0 ) t.right = remove( x, t.right ); // right child re-assigned // TWO CASES BELOW ARE POSSIBLE WHEN X EQUALS TO T.ELEMENT else if( t.left != null && t.right != null ) // Node to remove has TWO CHILDREN { // Step (1): // Find the min element in the right subtree, and // OVERWRITE t's data with the right-subtree-min. t.element = findMin( t.right ).element; // Step (2): // Then remove the right-subtree-min node. t.right = remove( t.element, t.right ); } else // Node to remove has either 1 or 0 CHILD t = ( t.left != null ) ? t.left : t.right; return t; // Returns the reference to the current node. }
private BinaryNode findMin( BinaryNode t ) { if( t == null ) return null; else if( t.left == null ) return t; return findMin( t.left ); }
private BinaryNode findMax( BinaryNode t ) { if( t != null ) while( t.right != null ) t = t.right;
return t; }
private BinaryNode find( Comparable x, BinaryNode t ) { if( t == null ) return null; if( x.compareTo( t.element ) < 0 ) return find( x, t.left ); // NEEDS 'RETURN' else if( x.compareTo( t.element ) > 0 ) return find( x, t.right ); // NEEDS 'RETURN' else return t; // Match -- return the (existing) node with x }
/** The tree root. **/ private BinaryNode root; }
Balanced search trees are trees whose height in the worst case is O(log n)and for which the operations INSERT, DELETE, and SEARCH can be implemented in O(log n)time. Complete binary trees, if used as search trees, cannot be updated after an insertion or deletion in time less than Ω(n)They are too rigid. The key to the design of balanced search trees is the introduction of glue, or degrees of freedom. This glue takes the form of red nodes in a red-black tree, nodes with 2 children (instead of three) in 2-3 trees, and nodes with a height-imbalance of one in AVL trees.
Binary search trees (see Figure 1) work well for many applications but they
are limiting because of their bad worst-case performance (height = O(n)). A
binary search tree with this worst-case structure is no more efficient than a
regular linked list.
There exist over one hundred types of balanced search trees. Some of the more common types are: AVL trees, B-trees, and red-black trees. B-trees are a category of tree designed to work well on magnetic disks and other direct-access secondary storage devices (Cormen et al., 1996, p:381).
Heights of balanced search treesAVL trees were invented by two computer chess specialists in Russia,
Adelson-Velskii and Landis in 1962 (hence the acronym AVL).
>
B-tree
A B-tree of order m is a tree exhibiting the following properties:
B-trees of order 4 are known as 2-3-4 trees, and a B-tree of order 3 is known as a 2-3 tree. The accompanying Java applet demonstrates insert operations on a 2-3 tree. In fact, 2-3 trees were "invented" by J.E. Hopcroft in 1970 (Cormen et al., 1996, p:399), prior to B-trees in 1972 by Bayer and McCreight.
Red-black trees are standard binary trees that satisfy the following conditions:
[W: 4.4] AVL Trees
Proof:
The maximum depth of an AVL tree with n nodes occurs when the tree is minimally populated. Let nd(H) denote the minimum number of nodes in an AVL tree of height H. Then we have
rewrite iteration nd(H) = nd(H-1) + nd(H-2) + 1 (1) = nd(H-2) + nd(H-3) + 1 + nd(H-3) + nd(H-4) + 1 + 1 = nd(H-2) + 2*nd(H-3) + nd(H-4) + 1 + 2 (2) = nd(H-3) + 3*nd(H-4) + 3*nd(H-5) + nd(H-6) + 1 + 2 + 4 (3) = nd(H-4) + 4*nd(H-5) + 6*nd(H-6) + 4*nd(H-7) + nd(H-8) + 1 + 2 + 4 + 8 (4) ... = nd(H/2) + ... + nd(0) + 1 + 2 + 4 + ... + 2^(H/2-1) (H/2) = nd(H/2) + ... + nd(0) + (2^(H/2) - 1) > 2^(H/2) - 1Solve for H.
nd(H) = n > 2^(H/2) - 1 ... from the result above n+1 > 2^(H/2) log (n+1) > H/2 2 * log (n+1) > H Therefore, H = O(log n)
Insert the following numbers in an empty AVL tree: 40, 30, 20, 70, 90, 50, 15
Sparse AVL trees are defined as AVL trees of height h with the fewest possible nodes. Figure 3 shows sparse AVL trees of heights 0, 1, 2, and 3.
We first analyze the number of nodes nk in a sparse AVL tree of height k.
From Figure 3, we can deduce the following recurrence relation:
which looks like the Fibonacci sequence given by:
Adding 1 on both sides of the equalities we obtain:
Taking to be , we rewrite the recurrence relation as:
which is the usual Fibonacci recurrence relation.
By inspecting the Fibonacci sequence, one suspects that it grows somehow "exponentially" i.e. that it is of the form: , for some suitable constants A and c that we have to find.
Replacing by in the Fibonacci recurrence relation, we get:
After cancelling A, dividing by on both sides, the following quadratic equation:
is solved with the usual method, and:
The theory for linear homogeneous recurrence relations (cf: Rosen, K. "Discrete Mathematics and its Applications", third edition.) says that the general solution of such a recurrence relation is given by:
Note that: is an integer. Also:
since , we have fast.
We still have to find the two unknowns and . Using the initial conditions in the recurrence relation, we know that and , so the constants are extracted from:
Solving we get: and,
Hence, a sparse AVL tree of height k has:
If an AVL tree in general has height k, and n nodes, then:
and therefore, after trivial operations,
Note: is known under the name golden ratio and powers of it are very close to be integers.