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