Exam2 ReviewGeneral TermsRepresentation Of a General Tree -- first child/next siblingBinary tree (BT)Representation of Binary TreesTraversalBinary search tree (BST)Basic FunctionsInsert in BST (recursive version)Delete in BSTSlide 11Delete in BST, examplesSlide 13Delete Tree, exampleBinary Search TreeAVL TreeSingle rotationSingle RotationSlide 19Single Rotation Doesn’t Work in Some CasesDouble RotationSlide 22What’s priority queueStructure PropertyComplete Binary TreeHeap-Order property21.2.1 The INSERT operation21.2.2 The DeleteMIN Operation21.3 the buildHeap Operation: Linear-Time Heap constructionExam2 ReviewDr. Bernard Chen Ph.D.University of Central ArkansasGeneral TermsPath length: the number of edges on the path from a node to another.Depth of a node: the length of the path from the root to the node.Height of a node: the length of the path form the node to the deepest leaf.Siblings: Nodes with the same parent.Size of a Node: the number of descendants the node has (including the node itself). The size of root is the size of a tree. The size of a leaf is 1.ABDFGHECNode Height Depth Size A 3 0 8 B 1 1 3 C 0 1 1 D 2 1 3 E 0 2 1 F 0 2 1 G 1 2 2 H 0 3 1Representation Of a General Tree-- first child/next sibling Example for this tree:ABDFGHECAnullFirst childNext siblingBEnullHnull nullCnullDnullFnull nullGnullCannot directly access D from A. ParentPtrKey valuesibling1st childBinary tree (BT)A binary tree is either empty, or it consists of a node called the root together with TWO binary trees called the left subtree and the right subtree of the root.A binary tree is either empty, or it consists of a node called the root together with TWO binary trees called the left subtree and the right subtree of the root.A binary tree is a tree in which no node can have more than two children.A binary tree is a tree in which no node can have more than two children.Representation of Binary TreesleavesleavesrootrootLeaves are nodes that have no children.Leaves are nodes that have no children.Parent Node: is the one between the node and the root of the tree.parentparentright childright childleft childleft childChild Node: is the one between the node and the leaves of the tree.ParentPtrKey valueRight CLeft CTraversalThree standard traversal orderpreorder - V L Rinorder - L V Rpostorder - L R VPreorder: traverse the node itself first, then all nodes in the LEFT subtree , then all nodes in the RIGHT subtree.Preorder: traverse the node itself first, then all nodes in the LEFT subtree , then all nodes in the RIGHT subtree.Inorder: traverse all nodes in the LEFT subtree first, then the node itself, then all nodes in the RIGHT subtree.Inorder: traverse all nodes in the LEFT subtree first, then the node itself, then all nodes in the RIGHT subtree.Postorder: traverse all nodes in the LEFT subtree first, then all nodes in the RIGHT subtree, then the node itself, Postorder: traverse all nodes in the LEFT subtree first, then all nodes in the RIGHT subtree, then the node itself, VRLA 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 9Basic FunctionsSearchFind MinFind MaxInsert(x)DeleteInsert 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( );}6311615892105 124 7 1417New nodes are always added as leaves.New nodes are always added as leaves.Delete in BSTCase 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.Delete in BSTLLCase 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.Delete in BST, examples616159105 127 14176161591012714176161591012717Case 2: delete a node that has only one subtree. Case 2: delete a node that has only one subtree.Delete 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 Find the min node in right subtree, then swap it with the target node, and remove the target nodeRLR’LMin in RDelete Tree, example631151492105 124 8167151410123124169867Case 3: delete a node that has nonempty left and right subtrees.Case 3: delete a node that has nonempty left and right subtrees.Binary Search TreeBinary search tree, using simple insert and delete proceduresthe tree is nearly balance add - fast O(log n)delete a target - fast O(log n)search - fast O(log n)the tree is highly unbalance, it becomes a singly linked list (the worst case)add, delete and search - slow O(n) effectively using sequential search to find a locationAVL TreeAVL Tree are BST with an additional balance condition to ensure the depth of the tree is O(log2N)Balance Condition: for any node in the tree, the height of the left and right subtrees can differ by at most 1.Must ensure that after insertion and deletion of a node, the balance condition is preservedSingle rotationk2k1ABCk1k2AB CSingle RotationyB CxA354 76 9218xBAyC354769218Single
View Full Document