Unformatted text preview:

BST TreesBinary search tree (BST)Binary search treeSome examplesIs this a BST?Search BSTBasic FunctionsC++ Implementation of BST SearchBalance treeBinary Search Tree Class - FindMin/MaxInsert & Delete in BSTInsert in BST (recursive version)Delete in BSTSlide 14Delete in BST, examplesSlide 16Delete Tree, exampleOrder statisticsBinary Search Tree1BST Trees53 81 4 92A binary search tree is a binary tree in which every node satisfies the following:• the key of every node in the left subtree is smaller than the key of this node• the key of every node in the right subtree is larger than the key of this nodeNote: Duplication nodes ?A binary search tree is a binary tree in which every node satisfies the following:• the key of every node in the left subtree is smaller than the key of this node• the key of every node in the right subtree is larger than the key of this nodeNote: Duplication nodes ?Binary search tree (BST)53 81 4 93Binary search tree53 81 4 9The left subtree and the right subtree are also BST (Recursion)No two nodes in a BST have the same key If we traverse a BST inorder, we list the key in ascending order4Some examples815102 126 143416179358842 61 3 751210 149 11 15135Is this a BST?53 81 7 9This is NOT BST!Every node satisfies the following: -- the key of the left node is smaller than the its own key -- the key of the right node is larger than its own keyEvery node satisfies the following: -- the key of the left node is smaller than the its own key -- the key of the right node is larger than its own keyThis is an incorrect check of BST.This is an incorrect check of BST.6Search BST842 61 3 751210 149 11 1513targetTo find a key in a BST, we start at the root. Compare the target key with the key of the current node.- target == p->key, Done.- target < p->key, go left- target > p->key, go rightTo find a key in a BST, we start at the root. Compare the target key with the key of the current node.- target == p->key, Done.- target < p->key, go left- target > p->key, go rightNote that the principle behind is similar to binary search...Note that the principle behind is similar to binary search...5Find7Basic FunctionsSearchFind MinFind MaxInsert(x)Delete8C++ Implementation of BST Search // Internal method to find an item in a subtree. // x is item to search for // t is the node that roots the tree // Return node containing the matched item. template <class Comparable> BinaryNode<Comparable> * BinarySearchTree<Comparable>:: find( const Comparable & x, Node *t ) const { while( t != NULL ) { if( x < t->element ) // element is the key value for each node t = t->left; else if( t->element < x ) t = t->right; else return t; // Match } return NULL; // Not found } // Internal method to find an item in a subtree. // x is item to search for // t is the node that roots the tree // Return node containing the matched item. template <class Comparable> BinaryNode<Comparable> * BinarySearchTree<Comparable>:: find( const Comparable & x, Node *t ) const { while( t != NULL ) { if( x < t->element ) // element is the key value for each node t = t->left; else if( t->element < x ) t = t->right; else return t; // Match } return NULL; // Not found }9Balance tree842 61 3 751210 149 11 1513113152The efficiency of BST search depends on the shape of the tree. If the tree is balance, (minimum height, very bushy), the search is fast (log(n) steps). If the tree is a long narrow chain, the search is slow (n steps)The efficiency of BST search depends on the shape of the tree. If the tree is balance, (minimum height, very bushy), the search is fast (log(n) steps). If the tree is a long narrow chain, the search is slow (n steps)14345log(16)=4Compare this with sequential and binary search ...Compare this with sequential and binary search ...10Binary Search Tree Class - FindMin/Maxtemplate <class Comparable>BinaryNode<Comparable> * BinarySearchTree<Comparable>::findMin( Node *t ) const{if( t != NULL ){ while( t->left != NULL ) t = t->left; // the leftmost node}return t;}template <class Comparable>BinaryNode<Comparable> * BinarySearchTree<Comparable>::findMax( Node *t ) const{ If( t != NULL ) while( t->right != NULL ) t = t->right; // the rightmost node return t;}11Insert & Delete in BSTFirst we’ll study simple-minded Insert and Delete procedure. They may result in highly unbalanced treeThen we’ll study a special kind of BST called AVL tree which maintains near balance in inserting and deleting.12Insert in BST (recursive version)// Internal method to insert into a subtree// x is the item to insert// t is the node that roots the tree// Set the new root// Throw an exception if x is already in ttemplate <class Comparable>void BinarySearchTree<Comparable>::insert( const Comparable & x, Node * & t ) const {if( t == NULL )t = new Node( x, NULL, NULL );else if( x < t->element )insert( x, t->left );else if( x > t->element)insert( x, t->right );elsethrow DuplicateItemException( );}631 15892105 124 7 1417New nodes are always added as leaves.New nodes are always added as leaves.13Delete in BSTCase 1: If it has no children, that is, it is a leaf, we just remove it.Case 1: If it has no children, that is, it is a leaf, we just remove it.14Delete in BSTLLCase 2: If it has only one child, (i.e. only one subtree), we splice out it. That is, we attach that subtree to the parent of the node. Case 2: If it has only one child, (i.e. only one subtree), we splice out it. That is, we attach that subtree to the parent of the node.15Delete in BST, examples616159105 127 14176161591012714176161591012717Case 2: delete a node that has only one subtree. Case 2: delete a node that has only one subtree.16Delete in BSTCase 3: If it has nonempty left and right subtrees. • Find the minimum node in right subtree, then copy its key value to X, and remove the min node from right subtree.• Or Find the min node in right subtree, then swap it with the target node, and remove the target nodeCase 3: If it has nonempty left and right subtrees. • Find the minimum node in right subtree, then copy its key value to X, and remove the min node from right subtree.• Or


View Full Document

GSU CSC 2320 - CSCI2320 Chapter 19 BST

Download CSCI2320 Chapter 19 BST
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CSCI2320 Chapter 19 BST and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CSCI2320 Chapter 19 BST 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?