Data Structures And Algorithms 6
Ming Zhang "Data Structures and Algorithms"Data Structuresand Algorithms（6）Instructor: Ming ZhangTextbook Authors: Ming Zhang, Tengjiao Wang and Haiyan ZhaoHigher Education Press, 2008.6 (the "Eleventh Five-Year" national planning 4830050x/2T2014/
Chapter 6Trees目录页AChapter 6 Trees General Definitions and Terminology of Tree––––Trees and ForestEquivalent Transformation between a Forest and a BinaryTreeAbstract Data Type of TreeGeneral Tree Traversals Linked Storage Structure of Tree Sequential Storage Structure of Tree K-ary Trees2Ming Zhang “Data Structures and Algorithms”CBEDIFJG H
Chapter 6Trees目录页6.1 General Definitions and Terminology of TreeTrees and Forest A tree T is a finite set of one or more nodes： there is one specific node R, called the root of T If the set T-{R} is not empty, these nodes arepartitioned into m 0 disjoint finite subsets T1，T2， ，Tm, each of which is a tree. The subsets Ti are saidto be subtrees of T. Directed ordered trees: the relative order of subtreesis important An ordered tree with degree 2 is not a binary tree After the first child node is deleted The second child node will take the first child node’splace3Ming Zhang “Data Structures and Algorithms”ABDICE F G HJ
Chapter 6Trees目录页6.1 General Definitions and Terminology of TreeLogical Structure of Tree A finite set K of n nodes, and a relation r satisfying thefollowing conditions:– There is a unique node k0 K, who has no predecessorin relation r. Node k0 is called the root of the tree.– Except k0, all the other nodes in K has a uniquepredecessor in relation r An example as in the figure on the right– Node set K { A, B, C, D, E, F, G, H, I, J }– The relation on K: r { A, B , A, C , B, D , B, E , B, F , C, G , C, H , E, I , E, J }4Ming Zhang “Data Structures and Algorithms”ACBEDIFJG H
Chapter 6Trees目录页 Node––If k, k′ r, we call that k is the parent node of k′, and k′ is thechild node of kSibling node, previous/next sibling node ATerminology of TreeChild node, parent node, the first child node –6.1 General Definitions and Terminology of TreeIf k, k′ r and k, k″ r, we call k′ and k″ are sibling nodesBranch node, leaf node Nodes who have no subtrees are called leaf nodes Other nodes are called branch nodes5Ming Zhang “Data Structures and Algorithms”CBEDIFJG H
Chapter 6Trees目录页6.1 General Definitions and Terminology of TreeTerminology of Tree Edge– The ordered pair of two nodes is called an edge Path, path length– Except the node k0, for any other node k K, thereexists a node sequence k0, k1, , ks, s.t. k0 is the rootnode, ks k, and ki-1, ki r (1 i s).– This sequence is called a path from the root node tonode k, and the path length (the total number of edgesin the path) is s Ancestor, descendant– If there is a path from node k to node ks, we call that kis an ancestor of ks, and ks is a descendant of k6Ming Zhang “Data Structures and Algorithms”ACBEDIFJG H
Chapter 6Trees目录页6.1 General Definitions and Terminology of TreeTerminology of TreeA Degree: The degree of a node is the number ofchildren for that node. Level: The root node is at level 0– The level of any other node is the level of itsparent node plus 1 Depth: The depth of a node M in the tree is thepath length from the root to M. Height: The height of a tree is the depth of thedeepest node in the tree plus 1.7Ming Zhang “Data Structures and Algorithms”CBEDIFJG H
Chapter 6Trees目录页6.1 General Definitions and Terminology of TreeDifferent Representations of Trees Classic node-link representation Formal (set theory) representation Venn diagram representation Outline representation Nested parenthesis representation8Ming Zhang “Data Structures and Algorithms”
Chapter 66.1 General Definitions and Terminology of TreeTrees目录页Node-Link RepresentationACBEDFGHJI9Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页6.1 General Definitions and Terminology of TreeFormal RepresentationThe logical structure of a Tree is:Node set:K {A, B, C, D, E, F, G, H, I, J}The relation on K:N { A, B , A, C , B, D , B, E , B,F , C, G , C, H , E, I , E, J }10Ming Zhang “Data Structures and Algorithms”ACBEDIFJG H
Chapter 6Trees目录页6.1 General Definitions and Terminology of TreeVenn Diagram RepresentationAABICIJ11EDEDCBFGHMing Zhang “Data Structures and Algorithms”FJG H
Chapter 6Trees目录页6.1 General Definitions and Terminology of TreeNested (G)(H)))12Ming Zhang “Data Structures and Algorithms”CBIFJG H
Chapter 6Trees目录页6.1 General Definitions and Terminology of TreeThe conversion from Venndiagram to nested parenthesisABCIFGH(A(B (D)(E (I) (J))(F))(C(G)(H)) )13EIJMing Zhang “Data Structures and Algorithms”CBDEDAFJG H
Chapter 6Trees目录页6.1 General Definitions and Terminology of TreeOutline RepresentationACBABCEDDEIJFIGH14Ming Zhang “Data Structures and Algorithms”FJG H
Chapter 6Trees目录页6.1 General Definitions and Terminology of TreeBook catalogue, Dewey representation6 Trees6.1 General Definitions and Terminology of Tree6.1.16.1.26.1.36.1.4Tree and ForestEquivalence Transformation between a Forest and a Binary TreeAbstract Data Type of the TreeGeneral Tree Traversals6.2 Linked Storage Structure of Tree6.2.16.2.26.2.36.2.46.2.5List of ChildrenStatic Left-Child/Right-Sibling representationDynamic representationDynamic Left-Child/Right-Sibling representationParent Pointer representation and its Application in Union-Find Sets6.3 Sequential Storage Structure of Tree6.3.16.3.26.3.36.3.4Preorder Sequence with rlink representationDouble-tagging Preorder Sequence representationPostorder Sequence with Degree representationDouble-tagging Levelorder Sequence representation6.4 K-ary Trees6.5 Knowledge Conclusion of Tree15Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页6.1 General Definitions and Terminology of TreeEquivalent Transformation between aForest and a Binary Tree Forest: A forest is a collection of one or moredisjoint trees. (usually ordered)The correspondence between trees and a forests– Removing the root node from a tree, itssubtrees become a forest.– Adding an extra node as the root of the treesin a forest, the forest becomes a tree.There is a one-to-one mapping between forestsand binary trees– So that all the operations on forests can betransformed to the operations on binary trees16ADB1Ming Zhang “Data Structures and Algorithms”CEKHFGJ
Chapter 6Trees目录页6.1 General Definitions and Terminology of TreeHow to map a forest to a binary tree?AT1T2AB1DFCET11HKDB1GJECKHFT12J17GMing Zhang “Data Structures and Algorithms”
Chapter 66.1 General Definitions and Terminology of TreeTrees目录页The transformation from a forest to a binary tree Ordered set F {T1, T2, , Tn} is a forest with trees T1, T2, , Tn. We transform it to a binary tree B(F) recursively: If F is empty (i.e., n 0), B(F) is an empty binary tree. If F is not empty (i.e., n 0), the root of B(F) is the root W1 of the first tree T1 in F; the left subtree of B(F) is the binary tree B(FW1), where FW1 is a forest consisting of W1’s subtrees in T1; the right subtree of B(F) is the binary tree B(F’), where F’ {T2, , Tn}.AT1T2ADDBECBWHFGHWXZ ZYJKYJEFT11XKCT3T12G18Ming Zhang “Data Structures and Algorithms”
Chapter 66.1 General Definitions and Terminology of TreeTrees目录页Convert a forest to a binary treest step: Add a connection13rd step:betweenAdjustthendall siblingnodesdeletein theall2 step: Foreach node,positionforest.the connections betweenA thenode and its children, except theDfirst child.AB1B1FCEDGECKHJKHFJ19Ming Zhang “Data Structures and Algorithms”G
Chapter 66.1 General Definitions and Terminology of TreeTrees目录页The transformation from a binary tree to a forest Assume B is a binary tree, r is the root of B, BL is the left sub-tree of r, BR is theright sub-tree of r. We can transform B to a corresponding forest F(B) as follows,If B is empty, F(B) is an empty forest.If B is not empty, F(B) consists of trees {T1} F(BR),where the root of T1 is r, the subtrees of r are F(BL) ADBT1WECKHT11YGCBXFJT2AEHT3DGFXWYJKT12Z20Ming Zhang “Data Structures and Algorithms”Z
Chapter 66.1 General Definitions and Terminology of TreeTrees目录页Convert a binary tree to a forest1 step:If the3rd step:Adjustthenode x is the leftchildof itsparentnd step:position2deleteall y, thenconnect the rightchild of x, theconnectionsbetweenright childrightchild of x, . , DArightparentsandoftheirto y.D children.stAB1CKB1EH FCEKHFGJGJ21Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页Questions1. Is a tree also a forest?1. Why do we establish the one-toone mapping between binary treesand forests?22Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页AChapter 6 Trees General Definitions and Terminology of Tree––––Linked Storage Structure of Tree Sequential Storage Structure of Tree K-ary Trees23Ming Zhang “Data Structures and Algorithms”EDTrees and ForestEquivalence Transformation between a Forest and a BinaryTreeAbstract Data Type of TreeGeneral Tree Traversals CBIFJG H
Chapter 6Trees目录页6.1 General Tree Definitions and TerminologyAbstract Data Type of Treetemplate class T class TreeNode {public:TreeNode(const T& value);virtual TreeNode() {};bool isLeaf();// The ADT of the tree nodeT Value();TreeNode T *LeftMostChild();TreeNode T *RightSibling();void setValue(const T& value);void setChild(TreeNode T *pointer);void setSibling(TreeNode T *pointer);void InsertFirst(TreeNode T *node);void InsertNext(TreeNode T ructorCheck whether the current node is theleaf node or notReturn the value of the nodeReturn the left-most (first) childReturn the right siblingSet the value of the current nodeSet the left childSet the right siblingInsert a node as the left childInsert a node as the right siblingMing Zhang “Data Structures and Algorithms”
Chapter 6Tree目录页6.1 General Tree Definitions and TerminologyAbstract Data Type of Treetemplate class T class Tree {public:Tree();// Constructorvirtual Tree();// DestructorTreeNode T * getRoot();// Return the root nodevoid CreateRoot(const T& rootValue);// Create a root node whose value is rootValuebool isEmpty();// Check whether it is an empty treeTreeNode T * Parent(TreeNode T *current);// Return parent nodeTreeNode T * PrevSibling(TreeNode T *current); // Return the previous siblingvoid DeleteSubTree(TreeNode T *subroot);// Delete the subtree rooted at “subroot”void RootFirstTraverse(TreeNode T *root);// Depth-first preorder traversalvoid RootLastTraverse(TreeNode T *root);// Depth-first postorder traversalvoid WidthTraverse(TreeNode T *root);// Breath-first traversal};25Ming Zhang “Data Structures and Algorithms”
Chapter 66.1 General Tree Definitions and TerminologyTrees目录页Traversal of a ForestDABCKAFEHDBGJECKHJFGPreorder sequence: A B C K D E H F J G Postorder sequence: B K C A H E J F G D 26Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页 Preorder binary tree traversalPostorder forest traversal– Forest Traversal vs.Binary Tree TraversalPreorder forest traversal– 6.1 General Tree Definitions and TerminologyInorder binary tree traversalInorder forest traversal?–We cannot define between which two child nodesshould the root locate.27Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页6.1 General Tree Definitions and TerminologyDepth-First Preorder Forest Traversaltemplate class T void Tree T ::RootFirstTraverse(TreeNode T * root) {while (root ! NULL) {Visit(root- Value());// Visit the current node// Traverse the subtree forest of the root node of// the first tree (except the root node)RootFirstTraverse(root- LeftMostChild());root root- RightSibling();// Traverse other trees}}28CEDXJ FMLKMing Zhang “Data Structures and Algorithms”GLIN
Chapter 6Trees目录页6.1 General Tree Definitions and TerminologyDepth-First Postorder TraversalCEtemplate class T void Tree T ::RootLastTraverse(FJTreeNode T * root) {while (root ! NULL) {K// Traverse the subtree forest of the root node// of the first treeRootLastTraverse(root- LeftMostChild());Visit(root- Value());// Visit the current noderoot root- RightSibling(); // Traverse other trees}Ming Zhang “Data Structures and Algorithms”29}DXMLGLIN
Chapter 6Trees目录页6.1 General Tree Definitions and TerminologyBreadth-First Forest Traversal Breadth-first forest traversal– Also be called level-order traversal a) First, visit the nodes who are at level 0b) Second, visit the nodes who are at level 1c) Continue until all the nodes at the deepestlevel are visited30Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页6.1 General Tree Definitions and TerminologyBreadth-First Forest TraversalDABCGEFKAH JBDECKHJFG Breadth-first forest traversal sequence: A D B C E F G K H J Look at the right diagonal of the binary tree storagestructure31Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页6.1 General Tree Definitions and TerminologyBreadth-first forest traversaltemplate class T void Tree T ::WidthTraverse(TreeNode T * root) {using std::queue;// Use STL queuequeue TreeNode T * aQueue;TreeNode T * pointer root;while (pointer ! NULL) {aQueue.push(pointer);// Put the current node go into the queuepointer pointer- RightSibling();// pointer pointing to right sibling}while (!aQueue.empty()) {pointer aQueue.front();// Get the first element of the queueaQueue.pop();// Pop the current element out of the queueVisit(pointer- Value());// Visit the current nodepointer pointer- LeftMostChild(); // pointer pointing to the first childwhile (pointer ! NULL) {// Put the child nodes of the current node// into the queueaQueue.push(pointer);pointer pointer- RightSibling();} } }32Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页Questions1. Can we use the template of preorderbinary tree traversal to accomplish thepreorder forest traversal?2. Can we use the template of inorderbinary tree traversal to accomplish thepostorder forest traversal?3. How to accomplish non-recursivedepth-first forest search?33Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页6.1 General Tree Definitions and Terminologywrongdifferent opinions of breadth-first searchDABCGEFKH JAABDECKHJDBECKFGHJ Cannot use the template of breadth-first binary tree traversal. For example，– In the left figure, the breadth-first forest traversal: A D B C E F G K H J Look at the tilt dotted circles in the middle– In the right figure, the breadth-first binary tree traversal: A B D C E K H F J G Look at the parallel dotted circles on the right34Ming Zhang “Data Structures and Algorithms”FG
Chapter 6Trees目录页Chapter 6 Trees General Definitions and Terminology of TreeLinked Storage Structure of Tree––––– AList of ChildrenStatic Left-Child/Right-Sibling representationDynamic representationDynamic Left-Child/Right-Sibling representationParent Pointer representation and its Application inUnion/Find SetsSequential Storage Structure of TreeK-ary Trees35Ming Zhang “Data Structures and Algorithms”CBEDIFJG H
Chapter 66.2 Linked Storage Structure of TreeTrees目录页“List of Children” representationList of children is the adjacency list of a directed F26G210117H28I39J310K611L636Ming Zhang “Data Structures and Algorithms”5
Chapter 66.2 Linked Storage Structure of TreeTrees目录页Static Left-Child/Right-Sibling representation Child node table stored in an arrayABGCEDF37HJI父 右兄弟左子值结点结点 结点AB 0C 0D 0E 2F 2GH 6I 6J 7Ming Zhang “Data Structures and Algorithms”
Chapter 66.2 Linked Storage Structure of TreeTrees目录页Dynamic representationAllocate dynamic storage to each node – If the number of child nodes changes, we shouldreallocate the storageA 2ABDICEJB 2FKGHL(a) 树D 2I 0C 3E 0J 0F 0G 2K 0H 0L 0(b) 树的实现38Ming Zhang “Data Structures and Algorithms”
Chapter 66.2 Linked Storage Structure of TreeTrees目录页Dynamic Left-Child/Right-Sibling representation The left child in the tree is the first child of the node, the right child is the right sibling of that node.The right sibling of the root node is the root node of next tree in the forestpChildinfoABpSiblingDCBH J39DECGEFKAKHFJMing Zhang “Data Structures and Algorithms”G
Chapter 6Trees目录页6.2 Linked Storage Structure of TreeThe key details of Dynamic LeftChild/Right-Sibling representation// Add following private variables to the class TreeNodeprivate:T m Value;// the value of the nodeTreeNode T *pChild;// the pointer of the first left childTreeNode T *pSibling;// the pointer of the right sibling40Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页6.2 Linked Storage Structure of TreeFind the parent node of the current nodetemplate class T TreeNode T * Tree T ::Parent(TreeNode T *current) {using std::queue;// use the queue of STLqueue TreeNode T * aQueue;TreeNode T *pointer root;TreeNode T *father upperlevelpointer NULL;// record the parent nodeif (current ! NULL && pointer ! current) {while (pointer ! NULL) {// Put all root nodes in the forest into the queueif (current pointer)// the parent node of the root node is emptybreak;aQueue.push(pointer);// Put the current node into the queuepointer pointer- RightSibling();// let the pointer point to the right sibling node}41Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页6.2 Linked Storage Structure of TreeFind the parent node of the current nodewhile (!aQueue.empty()) {pointer aQueue.front();// get the pointer of the first node in the queueaQueue.pop();// Pop the current node out of the queueAupperlevelpointer pointer;// pointing to the node at upper levelpointer pointer- LeftMostChild(); // pointing to the first childDBwhile (pointer) {// Put the child node of the current node into the queueECif (current pointer) {father upperlevelpointer; // return the parent nodeKFHbreak;}else {aQueue.push(pointer);JGpointer pointer- RightSibling();}}}}aQueue. clear( );return father;}// clear the queue, optional(local variable)42Ming Zhang “Data Structures and Algorithms”WXY
Chapter 6Trees目录页6.2 Linked Storage Structure of TreeDelete all the nodes in a sub-foresttemplate class T void Tree T ::DestroyNodes(TreeNode T * root) {if (root) {DestroyNodes(root- LeftMostChild());//delete the first subtreeDestroyNodes(root- RightSibling()); //delete other subtrees recursivelydelete root; // delete the root node}}43Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页6.2 Linked Storage Structure of TreeDelete the subtree whose root node is subroottemplate class T void Tree T ::DeleteSubTree(TreeNode T *subroot) {if (subroot NULL) return;// if the subtree to be deleted is empty, then returnTreeNode T *pointer Parent (subroot); // find the parent node of subrootif (pointer NULL) {// if subroot does not have a parent node, it is a root nodepointer root;while (pointer- RightSibling() ! subroot)// find in the right siblings of subrootpointer pointer- RightSibling();pointer- setSibling(subroot- RightSibling()); // renew the right sibling of pointer}else if (pointer- LeftMostChild() subroot) // if subroot is the first childpointer- setChild(subroot- RightSibling()); // renew the right sibling of pointerelse {// the condition where subroot has a left siblingpointer pointer- LeftMostChild();// sift down to the most left siblingwhile (pointer- RightSibling() ! subroot))// find in the right siblings of subrootpointer pointer- RightSibling();pointer- setSibling(subroot- RightSibling()); // renew the right sibling of pointer}subroot- setSibling(NULL);// very important. it will go wrong without this statementDestroyNodes(subroot); // delete all the nodes of in the subforest rooted at subrootMing Zhang “Data Structures and Algorithms”}44
Chapter 6Trees目录页6.2 Linked Storage Structure of TreeThinking: Can the followingalgorithm traverse the forest?template class T void Traverse(TreeNode T * rt) {if (rt NULL) return;Visit(rt);TreeNode * temp rt- LeftMostChild();while (temp ! NULL) {Traverse(temp);temp temp- RightSibling();}}45CDEMXJLIKMing Zhang “Data Structures and Algorithms”NLFG
Chapter 66.2 Linked Storage Structure of TreeTrees目录页Thinking: use the traversaltemplate flexiblyExample: Specular mapping of a forestDDEGGEFAFBB46AMing Zhang “Data Structures and Algorithms”
Chapter 66.2 Linked Storage Structure of ABBA47Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页6.2 Linked Storage Structure of TreeThinking: delete the subtreerooted at “subroot”Pay attention to checking whether thesubtree to be deleted is empty or not,and whether the subroot have a parentpointer.Pay attention to the order of pointerupdates after deletion.48Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页Chapter 6 Trees General Definitions and Terminology of TreeLinked Storage Structure of Tree––––– AList of ChildrenStatic Left-Child/Right-Sibling representationDynamic representationDynamic Left-Child/Right-Sibling representationParent Pointer representation and its Application inUnion/Find SetsSequential Storage Structure of TreeK-ary Trees49Ming Zhang “Data Structures and Algorithms”CBEDIFJG H
Chapter 66.2 Linked Storage Structure of TreeTrees目录页Parent Pointer representationA representation that you only need to know the parent node For each node, you only need to store a pointer which pointsto its parent node, so that we call it parent pointerrepresentation Use an array to store the tree nodes, and each node includes avalue and a pointer which points to its parent node ABDICEJFKGH结点索引值父结点索引0 1 2 3 4 5 6 7 8 9 10 11A B C D E F G H I J K L0 0 1 1 2 2 2 3 3 6 6L50Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页6.2 Linked Storage Structure of TreeParent Pointer representation: Algorithm Find the root node of the current node– Start from a node, find a path from that node to its root node O(k), k is the height of the tree Check whether two nodes are in the same tree– If these two nodes have the same root node, then they are sure to be in thesame tree.– If these two nodes have different root nodes, then they are sure to be indifferent trees.51Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页6.2 Linked Storage Structure of TreeUnion/Find Sets Union/Find Sets is a special kind of sets, consisted ofsome disjoint subsets. The basic operations ofUnion/Find Sets are:– Find:Find the set the node belongs to– Union: Merge two sets Union/Find Sets is an important abstract data types– The application of Union/Find sets is mainly to solve theproblem of equivalence classes .52Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页6.2 Linked Storage Structure of TreeEquivalence relation There is a set S, having n elements, and a set R, having rrelations, which are defined based on S. And x, y, z, are theelements of the set S. The relation R will be an equivalence relation, if and only ifthe following conditions are true:a) (x, x) R for all (reflexivity)b) (y, x) R if and only if (x, y) R (symmetry)c) If (x, y) R and (y, z) R, then (x, z) R（transitivity） If (x, y) R, we say elements x and y are equivalent53Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页6.2 Linked Storage Structure of TreeEquivalence Classes Equivalence class is the largest set consisting ofelements which are equivalent to each other.The ‘largest’ means that there is no otherelement equivalent to any element in the set. An equivalence class derived from x S based onthe relation R– [x]R {y y S xRy}– R partition S into r disjoint sets S1, S2, Sr,and the union of these sets equals to S54Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页6.2 Linked Storage Structure of TreeUse tree to represent theUnion/Find of equivalence classes Use a tree to represent a set–– S1S2135–(a)The set can be represented by the root nodeIf two nodes are in the same tree, they belongto the same setStore in a static pointer arrayA node only needs to store the information ofits parent node5546Ming Zhang “Data Structures and Algorithms”(b)145783The representation of tree–272S3(c)68
Chapter 66.2 Linked Storage Structure of TreeTrees目录页UNION/FIND Algorithm(1)Process these 5 equivalence pairs (A, B),(C, K) , (J, F), (H, E), (D, G)024 5 6FG0 1 2 3 4 5 6(A,B) (C,K) (J,F)(E,H)(D,G)7A BC KD EH J8ACFEDBKJHG569Ming Zhang “Data Structures and Algorithms”
Chapter 66.2 Linked Storage Structure of TreeTrees目录页UNION/FIND Algorithm(1)Then, process two equivalence pairs (K, A) and (E, G)The root of the tree that K belongsto is C, A itself is a root node, andA！ C, so merge these two trees.0 0 24 5 64A BC KD EFGH J02467813557(K,A)(E,G)ABDCFKJGE9Ming Zhang “Data Structures and Algorithms”H
Chapter 6Trees目录页6.2 Linked Storage Structure of TreeParent pointer representation and Union/Find algorithm representationtemplate class T class ParTreeNode {private:Tvalue;ParTreeNode T * parent;int nCount;public:ParTreeNode();virtual ParTreeNode(){};TgetValue();void setValue(const T& val);ParTreeNode T * getParent();void setParent(ParTreeNode T * par);int getCount();void setCount(const int count);};58//Definition of tree node//The value of the node//The parent node pointer//The number of the nodes in the set//Constructor//Destructor//Return the value of the node//Set the value of the node//Return the parent node pointer//Set the parent node pointer//Return the number of nodes//Set the number of nodesMing Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页6.2 Linked Storage Structure of TreeParent pointer representation and Union/Find algorithm representationtemplate class T class ParTree {public:ParTreeNode T * array;int Size;ParTreeNode T *Find(ParTreeNode T * node) const;ParTree(const int size);virtual ParTree();void Union(int i,int j);// Definition of the tree// the array used to store the tree node// the size of the array// Find the root node of “node”// Constructor// Destructor// Union set i and j, and merge them// into the same subtreebool Different(int i,int j); // Check if node i and j belong to the same tree};59Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页6.2 Linked Storage Structure of TreeParent pointer representation and Union/Find algorithm representationtemplate class T ParTreeNode T *ParTree T ::Find(ParTreeNode T * node) const{ParTreeNode T * pointer node;while ( pointer- getParent() ! NULL )pointer pointer- getParent();return pointer;}60Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页6.2 Linked Storage Structure of TreeParent pointer representation and Union/Find algorithm representationtemplate class T void ParTree T ::Union(int i,int j) {ParTreeNode T * pointeri Find(&array[i]);// find the root node of node iParTreeNode T * pointerj Find(&array[j]);// find the root node of node jif (pointeri ! pointerj) {if(pointeri- getCount() pointerj- getCount()) {pointerj- setParent(pointeri);pointeri- setCount(pointeri- getCount() pointerj- getCount());}else {pointeri- setParent(pointerj);pointerj- setCount(pointeri- getCount() pointerj- getCount());}} }61Ming Zhang “Data Structures and Algorithms”
Chapter 66.2 Linked Storage Structure of TreeTrees目录页UNION/FIND Algorithm(2)Use weighted union rule to process (H, J)(H,J)The root nodeof the treeH locatesAccordingto weightedunionin is theE, andthat ofis F, E of! theF, sorule,numberofJnodesthatwhosetwo treesuniontreerootshouldnode isF issmaller, so let F point to D0 0 2A4 4 4 5 6A BC KD EFGH J02467813562BDCFKJGE9Ming Zhang “Data Structures and Algorithms”H
Chapter 6Trees目录页6.2 Linked Storage Structure of TreePath compression Find X––BAssume that X finally reaches the root node RAlong the path from X to R, make parentpointer of every node point to R ALow altitude trees come out63Ming Zhang “Data Structures and Algorithms”DCFKJGEH
Chapter 66.2 Linked Storage Structure of TreeTrees目录页UNION/FIND Algorithm(3)Use path compression to deal with Find(H)AB0 0 2DCFKJG4 4 4 45 6A BC KD EFGH J02467813EH64Ming Zhang “Data Structures and Algorithms”59
Chapter 6Trees目录页6.2 Linked Storage Structure of TreePath compressiontemplate class T ParTreeNode T *ParTree T ::FindPC(ParTreeNode T * node) const{if (node- getParent() NULL)return node;node- setParent(FindPC(node- getParent()));return node- getParent();}65ABDCFKJMing Zhang “Data Structures and Algorithms”GEH
Chapter 6Trees目录页6.2 Linked Storage Structure of TreePath compression make the expenditureof Find close to a constant Weight path compression The expenditure of n Find operations for nnodes is O(nα(n)), which is about Θ(nlog*n)– α(n) is the inverse of univariate Ackermann function, its growthrate is slower than logn, but not equals to constant– log*n is the number of operations that calculate log(n) before n logn 1– log*65536 4 (4 log operations) The algorithm of find needs at most n Findoperations, so it is very close to Θ(n)– In practical applications, α(n) is usually smaller than 466Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页6.2 Linked Storage Structure of TreeThinking Can we use dynamic pointer representationto accomplish parent pointerrepresentation? Consult books or websites, read differentoptimizations of weighted union rule andpath compression. Discuss their differences,advantages and disadvantages.67Ming Zhang “Data Structures and Algorithms”
Chapter 6Trees目录页AChapter 6 Trees General Definitions and Terminologyof TreeEDI Linked Storage Structure of Tree Sequential Storage Structure of Tree K-ary Trees68CBMing Zhang “Data Structures and Algorithms”FJG H
Chapter 6Trees目录页6.3 Sequential Storage Structure of TreeSequential Storage Structure of Tree Preorder sequence with right link representation Double-tagging preorder sequence representation
Ming Zhang “Data Structures and Algorithms” Trees Chapter 6 6.1 General Definitions and Terminology of Tree Terminology of Tree Degree: The degree of a node is the number of children for that node. Level: The root node is at level 0 – The level of any other node is the level of its parent node plus 1
CS@VT Data Structures & Algorithms 2000-2021 WD McQuain Course Information 3 CS 3114 Data Structures and Algorithms Advanced data structures and analysis of data structure and algorithm performance. Sorting, searching, hashing, and advanced tree structures and algorithms. File system organization and access methods.
Design and analysis of algorithms with an emphasis on data structures. Approaches to analyzing lower bounds on problems and upper bounds on algorithms. Classical algorithm design techniques including algorithms for sorting, searching, and other operations on data structures such as hash tables, trees, graphs, strings, and advanced data
algorithms are required to effectively use flash memories. These algorithms and data structures support efficient not-in-place updates of data, reduce the number of erasures, and level the wear of the blocks in the device. This survey presents these algorithms and data structures, many of which have only been described in patents until now.
Apr 16, 2009 · 1 Data Structures and Algorithms 3 1.1 A Philosophy of Data Structures 4 1.1.1 The Need for Data Structures 4 1.1.2 Costs and Benefits 6 1.2 Abstract Data Types and Data Structures 8 1.3 Design Patterns 12 1.3.1 Flyweight 13 1.3.2 Visitor 14 1.3.3 Composite 15 1.3.4 Strategy 16 1.4 Problems, Algorith
These lecture notes cover the key ideas involved in designing algorithms. We shall see how they depend on the design of suitable data structures, and how some structures and algorithms are more e cient than others for the same task. We will concentrate on a few basic tasks, such as storing, sorting and searching data, that underlie much of computer science, but the techniques discussed will be .
5. Implementation: Data Structures and Algorithms Each of the four phases of the algorithm relies on the clever application of traditional data structures and algorithms. Considering the above algorithm as the logical “interface” to the problem, the algorithm’s phases are again described below in terms of the solution’s .
important data structures and algorithms. It is safe to say the level of contents will lie somewhere between an undergraduate course in Data Structures and a graduate course in Algorithms. Since I have taught these topics to M.E. students with a non-CS back-ground, I believe the lecture notes is at that level. By implication, this lecture notes .
Wirth N.; Algorithms Data Structures Programs; Prentice-Hall, 1976. Main references used for the classes are in bold. Algorithms and Data Structures 9
