(See related pages)
|
|
|
| A binary search tree t is a binary tree such that either t is empty or
1. Each element in leftTree(t) is less than the root element of t 2. Each element in rightTree(t) is greater than the root element of t 3. Both leftTree(t) and rightTree(t) are binary search trees The BinarySearchTree class maintains a sorted collection of Comparable elements. The time estimates for searching, inserting, and deleting depend on the height of the tree. In the worst case—for example, if the tree is a chain—the height is linear in n, the number of elements in the tree. The average height of a binary search tree is logarithmic in n. So for the contains, add, and remove methods, worstTime(n) is linear in n and averageTime(n) is logarithmic in n. A binary search tree is balanced if its height is logarithmic in n, the number of elements in the tree. Often, the balancing is maintained with rotations. A rotation is an adjustment to the tree around an element that maintains the required ordering of elements. This chapter introduced one kind of balanced binary search tree: the AVL tree. An AVL tree is a binary search tree that either is empty or in which: 1. The heights of the left and right subtrees differ by at most 1, and 2. The left and right subtrees are AVL trees. The AVLTree class is a subclass of the BinarySearchTree class. The only overridden methods are those related to maintaining balance: add and deleteEntry. |