《数据结构的算法在C++中的应用》（英文版）Chapter 11 Search Trees

Chapter 11 Search trees

Chapter 11 Search Trees

11. 1 Binary search Trees 1. Definition a binary search tree is a binary tree that may be empty. a nonempty binary search tree satisfies the following properties 1 )Every element has a key and no two elements have the same key; therefore, all keys are distinct

11.1 Binary Search Trees 1.Definition: A binary search tree is a binary tree that may be empty.A nonempty binary search tree satisfies the following properties: 1)Every element has a key and no two elements have the same key; therefore,all keys are distinct

11. 1 Binary search Trees )The keys(if any)in the left subtree of the root are smaller than the key in the root 3)The keys(if any)in the right subtree of the root are larger than the key in the root 4The left and right subtrees of the root are also binary search trees

11.1 Binary Search Trees 2)The keys(if any)in the left subtree of the root are smaller than the key in the root. 3)The keys(if any)in the right subtree of the root are larger than the key in the root. 4)The left and right subtrees of the root are also binary search trees

11. 1 Binary search Trees Example 45 Inherit the linked representation of binary tree 12) 53) Leftchild data rightchild 3)③7 0 90 78)

11.1 Binary Search Trees • Example: 45 12 53 90 78 100 24 61 3 37 Leftchild data rightchild Inherit the linked representation of binary tree

11. 1 Binary search Trees An indexed binary search tree is derived from an ordinary binary search tree by adding the field Leftsize to each tree node Value in leftsize field number of the elements in the node's left subtree +1 leftSize leftchild data rightChild

11.1 Binary Search Trees • An indexed binary search tree is derived from an ordinary binary search tree by adding the field LeftSize to each tree node. • Value in Leftsize field=number of the elements in the node’s left subtree +1 leftSize leftChild data rightChild

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 }