BINARY SEARCH TREE PERFORMANCE

1 BINARY SEARCH Tree PerformancePage1 BINARY SEARCH TREE PERFORMANCEO perationBest TimeAverage TimeWorst Time(on a tree ofnnodes)FindInsertDeleteO(lgn)??O(lg n)??O(n)Fastest Running TimeThe find, insert and delete algorithms start at the tree root and a follow path down to, at worstcase, the leaf at the very lowest level. The total number of steps of these algorithms is, therefore,the largest level of the tree, which is called thedepthof the best (fastest) running time occurs when the BINARY SEARCH tree isfull in which case thesearch processes used by the algorithms perform like a BINARY 's verify this. Afull BINARY treeis one in which nodes completely fill every level.

2 Forexample, here are the unique full BINARY trees of which have treedepths of 0, 1 and 2:As you can verify by looking at the examples, a full tree has 1 node at level 0, 2 nodes at level 1,4 nodes at level 2 and so on. Thus, it will have 2dnodes at leveld. Adding these quantities, thetotal number of nodesnfor a full BINARY tree with depthdis:n= 20+ 21+ 22+ .. + 2d= 2d+1 1 For example,the full BINARY tree of depth 2 above has 23 1 = 7 nodes. The BINARY tree below isa full tree of depth 3 and has 24 1 = 15 SEARCH Tree PerformancePage2 Now, considering the formula above for the number of nodes in a full BINARY SEARCH tree:n= 2d+1 1 Solving ford, we get: )lg(1)1lg(1)1lg()2lg()1()1lg()2lg()1lg(2 111ndnddndnnndd For example, the depth of a full BINARY SEARCH tree with 15 nodes is otherwords, the depth of a BINARY SEARCH tree withnnodes can be no less than lg(n) and so therunning time of the find, insert and delete algorithms can be no less than lg(n).

3 A full BINARY SEARCH tree is said to bebalancedbecause every node's proper descendants aredivided evenly between its left and right subtrees. Thus, the SEARCH algorithm employed by thefind, insert and delete operations perform like a BINARY Running TimeAs a BINARY SEARCH tree becomes more and more unbalanced, theperformance of the find, insertand delete algorithms degrades until reaching the worst case of O(n), wherenis the number ofnodes in the example,he number of comparisons needed to find the node markedAinthe BINARY SEARCH trees below is 3,which is equal to the number of SEARCH Tree PerformancePage3 BINARY SEARCH trees, such as those above, in which the nodes are in order so that all links are toright children (or all are to left children)

4 , are calledskewed RunningTimeThe average running time of the BINARY SEARCH tree operations is difficult to establish because it isnot clear that all BINARY SEARCH trees are equally has been proven that when a binarysearch tree is constructed through a random sequence of insertions then the average depth of anynode is O(lgn). For example, Figure a 500-node randomly generated tree whoseaverage node depth (calculated over all nodes) is problem arises when considering the effect of deletionssince the deletion algorithm replacesa deleted node with one from its right subtree, thus favoring left imbalance. For example, the result of applying 250,000 random insert/remove operations to the tree of The tree still has 500 nodes but now has an average node depth of Allen Weiss,Data Structures and Algorithm Analysis in Java, Addison-Wesley, 1999, page , page , page SEARCH Tree PerformancePage4 Extreme left imbalance after deletion, however, does not always happen nor does it happen withall trees, so its effect on the average execution times is not yet understood.

5 In short, the averageexecution time of the BINARY SEARCH tree operations appears (but cannot be proven) to be O(lgn).44 For a list of references on thistopic, see Ibid, page SEARCH Tree PerformancePage5 Balanced versus Unbalanced TreesThe time complexities of operations find, insert and delete on a BINARY SEARCH tree is:At best O(lgn), which occur when the tree is fullAt worst O(n) which occur when the tree is skewedThought to be on average O(lgn)Abalancedbinary SEARCH tree is close to being full, although not necessarily completely full. Ithas, for each node, about the same number of nodes inits left subtree as in its right , the find, insert and delete operations on a balanced tree give close to O(lgn) more unbalanced the tree becomes, the longer the SEARCH time grows until, at worst, it isO(n), occurring whenthe tree is you can live with running times that average O(lgn) but may degenerate to O(n) in the worstcase, then the BINARY SEARCH tree is sufficient for your purposes.

6 If, however, you must haveO(lgn) as your worst-case running time, then you must use a balanced BINARY SEARCH SchemesOn pages 458 and 459, your author mentions other schemes for keeping a BINARY SEARCH treebalanced. Here is a summary:The first tobe invented was theAVL tree, named for Adelson-Velskii and Landis whoinvented it in 1962. The workings of the AVL scheme are visualized in David Galles'tool. For an explanation of this scheme, see scheme your book covers in Chapter 9 is known asred-black trees. Its workings arevisualized in your author's RB Tree Workshop author covers another scheme in Chapter 10 called2-3-4 treesA scheme calledB-treesis used for searching large external files ( files stored ondisk).

7 These are also covered in Chapter schemes include AA trees and 2-3 alternative to balancing is calledsplay trees, whichguarantees that anymconsecutive treeoperations has a worst-case time complexity of O(mlgn) without guaranteeing than each singleoperation has O(lgn) time complexity. Weiss covers this Allen Weiss,Data Structures and Algorithm Analysis in Java, Addison-Wesley, 1999, pages , pages pages 118-138.