Exam2 ReviewGeneral TermsRepresentation Of a General Tree -- first child/next siblingBinary tree (BT)Representation of Binary TreesTraversalText CompressionHow do we find the optimal coding tree?Constructing a Huffman CodeSlide 10Slide 11Binary search tree (BST)Basic FunctionsInsert in BST (recursive version)Delete in BSTSlide 16Delete in BST, examplesSlide 18Delete Tree, exampleBinary Search TreeAVL TreeSingle rotationSingle RotationSlide 24Single Rotation Doesn’t Work in Some CasesDouble RotationSlide 27What’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 ArkansasFall 2010General 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, VRLText CompressionOn a computer: changing the representation of a file so that it takes less space to store or/and less time to transmit.Original file can be reconstructed exactly from the compressed representationHow do we find the optimal coding tree?it is clear that the two symbols with the smallest frequencies must be at the bottom of the optimal tree, as children of the lowest internal nodeThis is a good sign that we have to use a bottom-up manner to build the optimal code!Huffman’s idea is based on a greedy approach, using the previous notices.Constructing a Huffman CodeAssume that frequencies of symbols are A: 50 B: 20 C: 10 D: 10 R: 30Smallest numbers are 10 and 10 (C and D)Constructing a Huffman CodeAssume that frequencies of symbols are A: 50 B: 20 C: 10 D: 10 R: 30C and D have already beenused, and the new node above them (call it C+D) has value 20The smallest values are B, C+DConstructing a Huffman CodeAssume that frequencies of symbols are A: 50 B: 20 C: 10 D: 10 R: 30Next, B+C+D (40) and R (30)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 ?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
View Full Document