11. 1 Binary Search Trees Example 420 15 25 1|^12[1^18~1^30
11.1 Binary Search Trees • Example: 4 20 2 15 1 ^ 25 1 ^ 12 ^ 1 ^ 18 ^ 1 ^ 30 ^
11. 1 Binary search Trees 2. ADT specification of BSTree(ADT 11.1) AbstractDataType BStreei Instances binary trees, each node has an element with a key field; all keys are distinct; keys in the left subtree of any node are smaller than the key in the node; those in the right subtree are larger
11.1 Binary Search Trees 2.ADT specification of BSTree(ADT 11.1) AbstractDataType BSTree{ instances binary trees,each node has an element with a key field;all keys are distinct;keys in the left subtree of any node are smaller than the key in the node; those in the right subtree are larger
11. 1 Binary search Trees operations Create: create an empty binary search tree Search(k, e); return in e the element with key k return false if the operation fails return true if it succeeds Insert(e): insert element e into the search tree Delete(k, e): delete the element with key k and return it in e Ascendo: Output all elements in ascending order of key
11.1 Binary Search Trees operations: Create(): create an empty binary search tree Search(k,e):return in e the element with key k return false if the operation fails, return true if it succeeds Insert(e): insert element e into the search tree Delete(k,e):delete the element with key k and return it in e Ascend():Output all elements in ascending order of key }
11. 1 Binary search Trees 2. ADT specification of IndexedBSTree (ADT112) AbstractData Type IndexedBSTree instances same as for Bs tree except that each node has a LeftSize field operations Create: create an empty indexed binary search tree
11.1 Binary Search Trees 2. ADT specification of IndexedBSTree (ADT 11.2) AbstractDataType IndexedBSTree{ instances same as for BSTree except that each node has a LeftSize field operations Create(): create an empty indexed binary search tree
11. 1 Binary search Trees Search(k, e): return in e the element with key k return false if the operation fails return true if it succeeds IndexSearch(k, e) return in e the kth element Insert(e): insert element e into the search tree Delete(k, e): delete the element with key k and return it in e IndexDelete(k, e): delete the kth element and return it In e Ascendo Output all elements in ascending order of key
11.1 Binary Search Trees Search(k,e):return in e the element with key k return false if the operation fails, return true if it succeeds IndexSearch(k,e): return in e the kth element Insert(e): insert element e into the search tree Delete(k,e): delete the element with key k and return it in e IndexDelete(k,e): delete the kth element and return it in e Ascend(): Output all elements in ascending order of key }