11. 1 Binary search Trees if(e<p>data)p=p> Leftchild else if(e>p>data) p=p>RightChild else throw badInputo l/get a node for e and attach to pp Binary treeNode<e> rnew binary Treenode<e>(e) if(roottree not empty if(e<pp> datapp Leftchild=r else pp>RightChild-=r; 3
11.1 Binary Search Trees if(e<p→data) p=p→LeftChild; else if(e>p→data) p=p→RightChild; else throw BadInput(); } //get a node for e and attach to pp BinaryTreeNode<E> *r=new BinaryTreeNode<E>(e); if(root){tree not empty if(e<pp→data)pp→LeftChild=r; else pp→RightChild=r;}
11. 1 Binary search Trees else /insertion into empty tree root-r return"this We can construct a binary seach tree by add a sequence of keys into a empty binary search tree
11.1 Binary Search Trees else //insertion into empty tree root=r; return *this; } • We can construct a binary seach tree by add a sequence of keys into a empty binary search tree
11. 1 Binary search Trees 3)Deletion It is necessary to adjust the binary search tree after deleting an element, so that the tree remained is still a binary tree. There is three cases for deleting node p P is a leaf P has exactly one nonempty subtree P has exactly two nonempty subtrees
11.1 Binary Search Trees 3)Deletion It is necessary to adjust the binary search tree after deleting an element, so that the tree remained is still a binary tree.There is three cases for deleting node p : • P is a leaf • P has exactly one nonempty subtree • P has exactly two nonempty subtrees
11. 1 Binary search Trees Example 5 4 17 60
11.1 Binary Search Trees • Example: 15 12 24 10 8 11 18 16 17 20 29 23 21 32 30 35 33
11. 1 Binary search Trees In case 3 we can replace the element to be deleted with either the largest element in the left subtree or the smallest element in the right subtree Next step is to delete the largest element in the left subtree or smallest element in the right subtree
11.1 Binary Search Trees • In case 3: we can replace the element to be deleted with either the largest element in the left subtree or the smallest element in the right subtree. Next step is to delete the largest element in the left subtree or smallest element in the right subtree