BINARY SEARCH TREE PERFORMANCE
BINARY SEARCH Tree PerformancePage1BINARY SEARCH TREE PERFORMANCEOperationBest 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.
Binary Search Tree Performance Page 3 Binary search trees, such as those above, in which the nodes are in order so that all links are to right children …
Download BINARY SEARCH TREE PERFORMANCE
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: