DOC PREVIEW
GSU CSC 2320 - CSCI2320 Exam2 Review

This preview shows page 1-2-16-17-18-33-34 out of 34 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 TermsPath 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 CTraversalThree standard traversal orderpreorder - V L Rinorder - L V Rpostorder - 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 CompressionOn 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 nodeThis 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 CodeAssume that frequencies of symbols are A: 50 B: 20 C: 10 D: 10 R: 30Smallest numbers are 10 and 10 (C and D)Constructing a Huffman CodeAssume that frequencies of symbols are A: 50 B: 20 C: 10 D: 10 R: 30C and D have already beenused, and the new node above them (call it C+D) has value 20The smallest values are B, C+DConstructing a Huffman CodeAssume that frequencies of symbols are A: 50 B: 20 C: 10 D: 10 R: 30Next, 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 FunctionsSearchFind MinFind MaxInsert(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 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.Delete 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.Delete 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.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

GSU CSC 2320 - CSCI2320 Exam2 Review

Download CSCI2320 Exam2 Review
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 Exam2 Review 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 Exam2 Review 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?