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