CHAPTER 6
Trees
NOTE: The material in this presentation is a compilation from the Zybook of “Principles of Data Structure”, the book “Data Structures and other objects using C++” by Michael Main and Walter Savitvch, and original content from your professor.
By Prof. Rafael Orta, M.S.
NOTE: The material in this presentation is a compilation from the Zybook of “Principles of Data Structure”, the book “Data Structures and other objects using C++” by Michael Main and Walter Savitvch, and original material from your professor.
Last week we covered
Agenda for this week
NOTE: The material in this presentation is a compilation from the Zybook of “Principles of Data Structure”, the book “Data Structures and other objects using C++” by Michael Main and Walter Savitvch, and original material from your professor.
Binary Trees
“In a list, each node has up to one successor. In a binary tree, each node has up to two children, known as a left child and a right child. "Binary" means two, referring to the two children.
Some more definitions related to a binary tree:
Leaf: A tree node with no children.
Internal node: A node with at least one child.
Parent: A node with a child is said to be that child's parent. A node's ancestors include the node's parent, the parent's parent, etc., up to the tree's root.
Root: The one tree node with no parent (the "top" node).”
Binary Trees
Binary Trees
Binary Trees
Identify the type of binary tree
File System Trees
“File systems
Trees are commonly used to represent hierarchical data. A tree can represent files and directories in a file system, since a file system is a hierarchy.”
File System Trees
Binary Space Partitioning
“Binary space partitioning
Binary space partitioning (BSP) is a technique of repeatedly separating a region of space into 2 parts and cataloging objects contained within the regions. A BSP tree is a binary tree used to store information for binary space partitioning. Each node in a BSP tree contains information about a region of space and which objects are contained in the region.
In graphics applications, a BSP tree can be used to store all objects in a multidimensional world. The BSP tree can then be used to efficiently determine which objects must be rendered on screen. The viewer's position in space is used to perform a lookup within the BSP tree. The lookup quickly eliminates a large a number of objects that are not visible and therefore should not be rendered.”
Binary Space Partitioning
Binary Trees
“Binary search trees
An especially useful form of binary tree is a binary search tree (BST), which has an ordering property that any node's left subtree keys ≤ the node's key, and the right subtree's keys ≥ the node's key. That property enables fast searching for an item, as will be shown later. "
Binary Trees
Binary Search Trees (BST)
“Best case BST search runtime
Searching a BST in the worst case requires H + 1 comparisons, meaning O(H) comparisons, where H is the tree height. Ex: A tree with a root node and one child has height 1; the worst case visits the root and the child: 1 + 1 = 2. A major BST benefit is that an N-node binary tree's height may be as small as O(log2N), yielding extremely fast searches. Ex: A 10,000 node list may require 10,000 comparisons, but a 10,000 node BST may require only 14 comparisons (O(log2 10,000+1) = 13.287….. Approx. 14 )
A binary tree's height can be minimized by keeping all levels full, except possibly the last level. Such an "all-but-last-level-full" binary tree's height is H=⌊log2N⌋.”
Binary Search Trees (BST)
“Successors and predecessors
A BST defines an ordering among nodes, from smallest to largest. A BST node's successor is the node that comes after in the BST ordering, so in A B C, A's successor is B, and B's successor is C. A BST node's predecessor is the node that comes before in the BST ordering.
If a node has a right subtree, the node's successor is that right subtree's leftmost child: Starting from the right subtree's root, follow left children until reaching a node with no left child (may be that subtree's root itself). If a node doesn't have a right subtree, the node's successor is the first ancestor having this node in a left subtree.
BST search algorithm
“Given a key, a search algorithm returns the first node found matching that key, or returns null if a matching node is not found. A simple BST search algorithm checks the current node (initially the tree's root), returning that node as a match, else assigning the current node with the left (if key is less) or right (if key is greater) child and repeating. If such a child is null, the algorithm returns null (matching node not found).”
BST insert algorithm
“Given a new node, a BST insert operation inserts the new node in a proper location obeying the BST ordering property. A simple BST insert algorithm compares the new node with the current node (initially the root).
BST remove algorithm
“Given a key, a BST remove operation removes the first-found matching node, restructuring the tree to preserve the BST ordering property. The algorithm first searches for a matching node just like the search algorithm. If found (call this node X), the algorithm performs one of the following sub-algorithms:
BST inorder traversal
“A tree traversal algorithm visits all nodes in the tree once and performs an operation on each node. An inorder traversal visits all nodes in a BST from smallest to largest, which is useful for example to print the tree's nodes in sorted order. Starting from the root, the algorithm recursively prints the left subtree, the current node, and the right subtree. “
BST height and insertion order
“Recall that a tree's height is the maximum edges from the root to any leaf. (Thus, a one-node tree has height 0.)
The minimum N-node binary tree height is h=⌊log2N⌋, achieved when each level is full except possibly the last. The maximum N-node binary tree height is N - 1 (the - 1 is because the root is at height 0).
Searching a BST is fast if the tree's height is near the minimum. Inserting items in random order naturally keeps a BST's height near the minimum. In contrast, inserting items in nearly-sorted order leads to a nearly-maximum tree height. “
BST height and insertion order
BST height and insertion order
“Given a node representing a BST subtree, the height can be computed as follows:
BST Recursion
“BST recursive search algorithm
BST search can be implemented using recursion. A single node and search key are passed as arguments to the recursive search function. Two base cases exist. The first base case is when the node is null, in which case null is returned. If the node is non-null, then the search key is compared to the node's key. The second base case is when the search key equals the node's key, in which case the node is returned. If the search key is less than the node's key, a recursive call is made on the node's left child. If the search key is greater than the node's key, a recursive call is made on the node's right child.”