Introduction to TreesBinary TreesCS 311 Data Structures and AlgorithmsLecture SlidesWednesday, November 11, 2009Glenn G. ChappellDepartment of Computer ScienceUniversity of Alaska [email protected]© 2005–2009 Glenn G. Chappell11 Nov 2009 CS 311 Fall 2009 2Unit OverviewHandling Data & SequencesMajor Topics Data abstraction Introduction to Sequences Smart arrays Array interface Basic array implementation Exception safety Allocation & efficiency Generic containers Linked Lists Node-based structures More on Linked Lists Sequences in the C++ STL Stacks QueuesDONE11 Nov 2009 CS 311 Fall 2009 3ReviewStacksA Stack is: A kind of container. A Last-In-First-Out (LIFO) structure. A restricted version of a Sequence.Conceptually, a Stack carries out the idea of top-down design.Three primary operations: push pop getTopA Stack can be implemented simply as a wrapper around some existing Sequence type.1. Start:Empty Stack.2. Push 2.3. Push 7.4. Pop.5. Pop.Empty again.6. Push 5.2272511 Nov 2009 CS 311 Fall 2009 4ReviewQueuesA Queue is: A kind of container. A restricted version of a Sequence: First-In-First-Out (FIFO).Conceptually, a Queue carries out the idea of waiting in line.Three primary operations: enqueue dequeue getFrontA Queue can be implemented: As a wrapper around some existing Sequence type. Using a circular buffer.1. Start:Empty Queue.2. Enqueue 2.3. Enqueue 7.4. Dequeue.5. Dequeue.Empty again.6. Enqueue 5.2F BF B7F27F BBF B5F B11 Nov 2009 CS 311 Fall 2009 5ReviewWhere Are We? — The Big ProblemOur problem for much of the rest of the semester: Store: a collection of data items, all of the same type. Operations: Access items [one item: retrieve/find, all items: traverse]. Add new item [insert]. Eliminate existing item [delete]. All this needs to be efficient in both time and space.A solution to this problem is a container.Generic containers: those in which client code can specify the type of data stored.11 Nov 2009 CS 311 Fall 2009 6Unit OverviewThe Basics of TreesMajor Topics Introduction to Trees Binary Trees Binary Search Trees Treesort11 Nov 2009 CS 311 Fall 2009 7Introduction to Trees What is a Tree?By a tree, mathematicians mean a structure like this: Each dot is called a vertex (note the Latin plural “vertices”) or a node. I will use vertex for the element of the tree as a conceptual object, and node for the small data substructure representing it. Each line is called an edge. Each edge joins two vertices. A tree is connected (all one piece) and there are no cycles.11 Nov 2009 CS 311 Fall 2009 8Introduction to Trees Rooted Trees — IntroductionOften we use trees torepresent hierarchicalstructures.We place one vertex atthe top, and we call it theroot. Each other vertex ofthe tree hangs from somevertex. The result is arooted tree.From now on in this class,“tree” means “rooted tree”.root11 Nov 2009 CS 311 Fall 2009 9Introduction to Trees Rooted Trees — Terminology [1/5]Some of the terminology forrooted trees comes fromplants. “Root” is an obvious example. Another: A vertex with nothinghanging off of it is called a leaf. Leaves are shown in green. What if a tree has just onevertex?11 Nov 2009 CS 311 Fall 2009 10Introduction to Trees Rooted Trees — Terminology [2/5]Other terminology comesfrom family trees. To illustrate this, we label avertex “v” in the tree at right. The vertex that v hangs from(shown in red) is v’s parent. Every vertex except the roothas exactly one parent. The vertices that hang fromv (shown in blue) are v’schildren. A leaf has no children. The other children of v’sparent (shown in orange) arev’s siblings.v11 Nov 2009 CS 311 Fall 2009 11Introduction to Trees Rooted Trees — Terminology [3/5]The parent of v, and itsparent, and its parent, etc.,are v’s ancestors. These are shown in red.v’s children, and theirchildren, and their children,etc., are v’s descendants. These are shown in blue.v11 Nov 2009 CS 311 Fall 2009 12Introduction to Trees Rooted Trees — Terminology [4/5]The vertices of a rootedtree come in levels. The root is at level 1. Each other vertex has a level1 greater than its parent. Level 3, which includes v, isshown in orange. We often draw vertices at thesame level in a horizontal row.The height of a tree is thenumber of levels. This tree has height 8. Note: Some people define“height” slightly differently.v1234567811 Nov 2009 CS 311 Fall 2009 13Introduction to Trees Rooted Trees — Terminology [5/5]A subtree consists of anode and all its descendants. Given a node n, the subtreerooted at n consists of n and allits descendants. Given a node n, a subtree of n isa subtree rooted at some child ofn. Shown in green is a subtree ofv. It is the subtree rooted at v’schild w.vw11 Nov 2009 CS 311 Fall 2009 14Introduction to Trees Rooted Trees — General TreesA “general tree” is a somewhat more precise version of what we have been talking about. A general tree consists of a node (called the root) and zero or more subtrees of the root, each of which is a general tree. Note that a general tree must have at least one node.The above is a recursive definition.11 Nov 2009 CS 311 Fall 2009 15Binary TreesOverviewOur next ADT is Binary Tree.We will cover: What a Binary Tree is. Three special kinds. Traversals. Implementation. Applications.What is missing above? “Binary Trees in the C++ STL”, because there aren’t any. Not in the interface, anyway. They are used internally.11 Nov 2009 CS 311 Fall 2009 16Binary TreesWhat a Binary Tree Is — IdeaA Binary Tree consists of a set T of nodes so that either: T is empty (no nodes), or T consists of a node r, the root, and two subtrees of r, each of which is a Binary Tree: the left subtree, and the right subtree.We make a strong distinction between left and right subtrees. Sometimes, we use them for very different things.An empty Binary Tree is a Binary Tree with no nodes.ababDifferentBinary TreesEmpty Binary Tree11 Nov 2009 CS 311 Fall 2009 17Binary TreesWhat a Binary Tree Is — ADTData A set of nodes.Operations Create (empty). Create, given a root and two subtrees. Destroy. isEmpty. getRootData & setRootData. Access to data in root node. attachLeft &