Chapter 11 MULTIWAY TREES 1. Orchards, Trees, and Binary Trees 2. Lexicographic Search Trees: Tries L3. External Searching: B-Trees I 4. Red-Black Trees I Pointers and Pitfalls
Chapter 11 MULTIWAY TREES 1. Orchards, Trees, and Binary Trees 2. Lexicographic Search Trees: Tries 3. External Searching: B-Trees 4. Red-Black Trees Pointers and Pitfalls
11.1 On the Classification of Species 1. On the Classification of Species Definition: oA(free) tree is any set of points(called vertices)and any set of pairs of distinct vertices(called edges or branches)such that (1) there is a sequence of edges(a path) from any vertex to any other, and(2 there are no circuits, that is, no paths starting from a vertex and returning to the same vertex
11.1 On the Classification of Species Definition: 1. On the Classification of Species •A (free) tree is any set of points (called vertices) and any set of pairs of distinct vertices (called edges or branches) such that (1) there is a sequence of edges (a path) from any vertex to any other, and (2) there are no circuits, that is, no paths starting from a vertex and returning to the same vertex
2 Ordered Trees oA rooted tree is a tree in which one vertex, called the root, is distinguished oAn ordered tree is a rooted tree in which the children of each vertex are assigned an order. oA forest is a set of trees. We usually assume that all trees in a forest are rooted .An orchard (also called an ordered forest) is an ordered set of ordered trees
•An ordered tree is a rooted tree in which the children of each vertex are assigned an order. •A forest is a set of trees. We usually assume that all trees in a forest are rooted. •An orchard (also called an ordered forest) is an ordered set of ordered trees. 2. Ordered Trees •A rooted tree is a tree in which one vertex, called the root, is distinguished
Free trecs with four or fower vortIces (Arrangement of vertices Is Irrelevant.) Rooted trees with four or fewor vortices (Root is at the top of tree Ordered trios with four or fewor vortices See pg 522 Fig 11.1
See pg.522 Fig.11.1
3. Forests and Orchards ● Multiple links first child and next sibling links o Correspondence with binary trees Linked implementation of ordered tree first child: black: next sibling: color
3. Forests and Orchards •Multiple links •first child and next sibling links •Correspondence with binary trees
Recursive Definitions Definition A rooted tree consists of a single vertex V, called the root of the tree, together with a forest F whose trees are called the subtrees of the root A forest F is a (possibly empty) set of rooted trees Definition An ordered tree T consists of a single vertex v, called the root of the tree, together with an orchard o whose trees are called the subtrees of the root v We may denote the ordered tree with the ordered pair T=vON An orchard o is either the empty set ;, or consists of an ordered tree T, called the first tree of the orchard, together with another orchard o(which contains the remaining trees of the orchard). We may denote the orchard with the ordered pair O=(T, O)
Recursive Definitions Definition A rooted tree consists of a single vertex v, called the root of the tree, together with a forest F , whose trees are called the subtrees of the root. A forest F is a (possibly empty) set of rooted trees. Definition An ordered tree T consists of a single vertex v, called the root of the tree, together with an orchard O,whose trees are called the subtrees of the root v. We may denote the ordered tree with the ordered pair T = {v,O}. An orchard O is either the empty set ;, or consists of an ordered tree T , called the first tree of the orchard, together with another orchard O’ (which contains the remaining trees of the orchard). We may denote the orchard with the ordered pair O = (T ,O’)
FIrst tree Orchard of I remalnIng Orchard of subtree --------=---- Adjoin Delete new Toot Ordered tree Orchard Ordered tree
4. The Formal Correspondence Definition a binary tree B is either the empty set; or consiste 数学归纳法 ot vertex v with two binary trees B1 and B2.c ray denote the binary tree with the ordered trip B=[v; B1; B2 Theorem 11.1 LS be any finite set of vertices.There is a one-to-one c rrespondence f from the set of orchards whose st t of vertices is s to the set of binary trees whose et of vertices is S Proof. Define f (o)=( Define f(V, 013, O)=[v, f(O,), f(O2)1 Show by mathematical induction on the number of vertices that fis a one-to-one correspondence
4. The Formal Correspondence Definition A binary tree B is either the empty set ; or consists of a root vertex v with two binary trees B1 and B2 . We may denote the binary tree with the ordered triple B = [v;B1;B2]. Theorem 11.1 Let S be any finite set of vertices. There is a one-to-one correspondence f from the set of orchards whose set of vertices is S to the set of binary trees whose set of vertices is S. Proof. Define f () = Define f ({v,O1 },O2 ) = [ v,f(O1 ) ,f(O2 ) ] Show by mathematical induction on the number of vertices that f is a one-to-one correspondence. 数学归纳法
5 Rotations e Draw the orchard so that the first child of each vertex is immediately below the vertex. . Draw a vertical link from each vertex to its first child and draw a horizontal link from each vertex to its next sibling o Remove the remaining original links o Rotate the diagram 45 degrees clockwise, so that the vertical links appear as left links and the horizontal links as right links Rotate 45 Orchard Colored links added broken lInks removed BInary tree
5.Rotations • Draw the orchard so that the first child of each vertex is immediately below the vertex. • Draw a vertical link from each vertex to its first child, and draw a horizontal link from each vertex to its next sibling. • Remove the remaining original links. • Rotate the diagram 45 degrees clockwise, so that the vertical links appear as left links and the horizontal links as right links
6. Summary Orchards and binary trees correspond by any of o first child and next sibling links o rotations of diagrams, o formal notational equivalence
6. Summary Orchards and binary trees correspond by any of: • first child and next sibling links, • rotations of diagrams, • formal notational equivalence