Trees - Chapter 5 Flashcards
In a list, each node has up to one successor. In a blank, each node has up to two children, known as a left child and a right child.
binary tree
Blank: A tree node with no children.
Leaf
Blank: A node with at least one child.
Internal node
Blank A node with a child is said to be that child’s blank.
Parent:
A node’s blank include the node’s parent, the parent’s parent, etc., up to the tree’s root.
ancestors
Blank: The one tree node with no parent (the “top” node).
Root
The link from a node to a child is called an blank.
edge
A node’s blank is the number of edges on the path from the root to the node
depth
The root node thus has depth blank.
0
All nodes with the same depth form a tree blank
level
A tree’s blank is the largest depth of any node.
height
A tree with just one node has height blank
0
A binary tree is blank if every node contains 0 or 2 children.
full
A binary tree is blank if all levels, except possibly the last level, contain all possible nodes and all nodes in the last level are as far left as possible.
complete
A binary tree is blank, if all internal nodes have 2 children and all leaf nodes are at the same level.
perfect
Trees are commonly used to represent blank
hierarchical data
A blank can represent files and directories in a file system, since a file system is a hierarchy.
tree
Blank is a technique of repeatedly separating a region of space into 2 parts and cataloging objects contained within the regions.
Binary space partitioning (BSP)
A blank is a binary tree used to store information for binary space partitioning.
BSP tree
Each node in a BSP tree contains information about a blank and which objects are contained in the region.
region of space
In graphics applications, a BSP tree can be used to store all objects in a blank. The BSP tree can then be used to efficiently determine which objects must be rendered on screen.
multidimensional world
Most of the tree data structures discussed in this book serve to store a collection of values. Numerous tree types exist to store blank in a structured way that allows for fast searching, inserting, and removing of values.
data collections
An especially useful form of binary tree is a blank, 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
binary search tree (BST)
To search nodes means to find a node with a desired key, if such a node exists. A BST may yield faster searches than a blank Searching a BST starts by visiting the root node (which is the first currentNode below):
list.
Searching a BST in the worst case requires H + 1 comparisons, meaning blank comparisons, where H is the tree height.
O(H)
A major BST benefit is that an N-node binary tree’s height may be as small as blank, yielding extremely fast searches.
O(logN)
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 blank
H = floor(log2 N)
BST defines an ordering among nodes, from smallest to largest. A BST node’s blank 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.
successor
A BST node’s blank is the node that comes before in the BST ordering.
predecessor
If a node has a right subtree, the node’s successor is that right subtree’s blank:
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 blank having this node in a left subtree.
ancestor
A simple BST blank 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).
search algorithm
Given a new node, a BST blank operation inserts the new node in a proper location obeying the BST ordering property.
insert
Blank: If the new node’s key is less than the current node, and the current node’s left child is null, the algorithm assigns that node’s left child with the new node.
Insert as left child
Blank: If the new node’s key is greater than or equal to the current node, and the current node’s right child is null, the algorithm assigns the node’s right child with the new node.
Insert as right child
Blank: If the left (or right) child is not null, the algorithm assigns the current node with that child and continues searching for a proper insert location.
Search for insert location
The BST insert algorithm traverses the tree from the root to a leaf node to find the insertion location. One node is visited per level. A BST with N nodes has at least blank levels and at most blank levels.
log2N
N
For a BST, the runtime complexity of insertion is best case blank
and worst case blank
O(logN)
O(N)
The space complexity of insertion for a BST is blank because only a single pointer is used to traverse the tree to find the insertion location.
O(1)
Given a key, a BST blank operation removes the first-found matching node, restructuring the tree to preserve the BST ordering property.
remove
Blank: If X has a parent (so X is not the root), the parent’s left or right child (whichever points to X) is assigned with null. Else, if X was the root, the root pointer is assigned with null, and the BST is now empty.
Remove a leaf node
Blank: If X has a parent (so X is not the root), the parent’s left or right child (whichever points to X) is assigned with X’s single child. Else, if X was the root, the root pointer is assigned with X’s single child.
Remove an internal node with single child
Blank: This case is the hardest. First, the algorithm locates X’s successor (the leftmost child of X’s right subtree), and copies the successor to X. Then, the algorithm recursively removes the successor from the right subtree.
Remove an internal node with two children
STRemove(tree, key) {
parent = null
currentNode = tree⇢root
while (currentNode != null) {
// Check if currentNode has an equal key
if (currentNode⇢key == key) {
if (currentNode⇢left is null && currentNode⇢right is null) {
// Remove leaf
if (parent is null) { // Node is root
tree⇢root = null
}
else if (parent⇢left == currentNode) {
parent⇢left = null
}
else {
parent⇢right = null
}
return true // Node found and removed
}
else if (currentNode⇢right is null) {
// Remove node with only left child
if (parent is null) { // Node is root
tree⇢root = currentNode⇢left
}
else if (parent⇢left == currentNode) {
parent⇢left = currentNode⇢left
}
else {
parent⇢right = currentNode⇢left
}
return true // Node found and removed
}
else if (currentNode⇢left is null) {
// Remove node with only right child
if (parent is null) { // Node is root
tree⇢root = currentNode⇢right
}
else if (parent⇢left == currentNode) {
parent⇢left = currentNode⇢right
}
else {
parent⇢right = currentNode⇢right
}
return true // Node found and removed
}
else {
// Remove node with two children
// Find successor (leftmost child of right subtree)
successor = currentNode⇢right
while (successor⇢left is not null) {
successor = successor⇢left
}
// Copy successor's key to current node
currentNode⇢key = successor⇢key
Parent = currentNode
// Reassign currentNode and key so that loop continues with new key
currentNode = currentNode⇢right
key = successor⇢key
}
return // Node found and removed
}
else if (currentNode⇢key < key) {
// Search right
parent = currentNode
currentNode = currentNode⇢right
}
else {
// Search left
parent = currentNode
currentNode = currentNode⇢left
} } return false // Node not found }
BST remove algorithm.
The blank traverses the tree from the root to find the node to remove. When the node being removed has two children, the node’s successor is found and a recursive call is made. One node is visited per level, and in the worst case scenario the tree is traversed twice from the root to a leaf.
BST remove algorithm
A BST with N nodes has at least log2N
levels and at most N levels. So removal’s worst case time complexity is blank for a BST with log2N
levels and worst case blank
for a tree with N levels.
O(logN)
O(N)
In BST removal, two pointers are used to traverse the tree during removal. When the node being removed has two children, a third pointer and a copy of one node’s data are also used, and one recursive call is made. So removal’s space complexity is always
blank.
O(1)
A blank algorithm visits all nodes in the tree once and performs an operation on each node.
tree traversal
An blank 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.
inorder traversal
The minimum N-node binary tree height is blank
, 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).
h = floor(log2 N)
Given a node representing a BST subtree, the height can be computed as follows:
If the node is null, return blank.
Otherwise recursively compute the left and right child subtree heights, and return blank.
-1
1 plus the greater of the 2 child subtrees’ heights
A BST implementation often includes a blank inside each node. A balanced BST, such as an AVL tree or red-black tree, may utilize the parent pointer to traverse up the tree from a particular node to find a node’s parent, grandparent, or siblings. The BST insertion and removal algorithms below insert or remove nodes in a BST with nodes containing parent pointers.
parent pointer
BST search can be implemented using blank. 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.
recursion
A recursive BST get-parent algorithm searches for a parent in a way similar to the normal BST search algorithm. But instead of comparing the search key with a candidate node’s key, the search key is compared with the keys of the candidate blank.
node’s children
BST insertion and removal can also be implemented using blank. The insertion algorithm uses recursion to traverse down the tree until the insertion location is found. The removal algorithm uses the recursive search functions to find the node and the node’s parent, then removes the node from the tree. If the node to remove is an internal node with 2 children, the node’s successor is recursively remove
recursion
A blank is a tree representing a set of strings.
trie (or prefix tree)
In a trie, each non-root node represents a single blank. Each node has at most one child per distinct alphabet character.
character
A blank is a node that represents a terminating character, which is the end of a string in the trie.
terminal node
Tries provide efficient storage and quick search for strings, and are often used to implement blank and blank
auto-complete and predictive text input.
Given a string, a trie blank operation creates a path from the root to a terminal node that visits all the string’s characters in sequence.
insert
current node pointer initially points to the root. A loop then iterates through the string’s characters. For each character C:
After all characters are processed, a terminal node is added and returned.
A new child node is added only if the current node does not have a child for C.
The current node pointer is assigned with the current node’s child for C.
Given a string, a blank operation returns the terminal node corresponding to that string, or null if the string is not in the trie.
trie search
Given a string, a trie blank removes the string’s corresponding terminal node and all non-root ancestors with 0 children.
remove operation
Implementations commonly use a lookup table for a trie node’s children, allowing retrieval of a child node from a character in blank time. Therefore, to insert, remove, or search for a string of length M in a trie takes blank time. The trie’s current size does not affect each operation’s time complexity.
O(1)
O(M)
A binary search tree can be implemented in Python using blank and blank.
a Node class and a BinarySearchTree class
The blank class contains a key value and data members for the left and right children nodes.
Node
The blank contains a data member for the tree’s root (a Node object).
BinarySearchTree class
The binary search tree search algorithm first assigns current_node with the root. A loop is then entered, and one of three cases occurs:
Case 1: The current node’s key matches the desired key, so current_node is returned from the method.
Case 2: The desired key is less than the current node’s key, so current_node is assigned with current_node.left.
Case 3: The desired key is greater than the current node’s key, so current_node is assigned with current_node.right.
The blank is used to insert a new node into the tree. If the tree is empty, then the root data member is assigned with the new node. If the tree is not empty, current_node is assigned with the root node, and a loop is entered. Inside the loop, if the new node’s key is less than the current node’s key, then the new node is inserted as the current node’s left child (if the current node has no left child), or current_node is assigned with current_node.left. If the new node’s key is greater than or equal to the current node’s key, then the new node is inserted as the current node’s right child (if the current node has no right child), or current_node is assigned with current_node.right.
insert() method
The remove() method is more complicated than search() and insert() because several cases exist. Different actions are taken depending on what the kind of node is being removed.
Case 1: The node being removed is a leaf. The parent’s left or right data member is assigned with None, depending on which side the node is.
Case 2: The node being removed has one child. The parent’s left or right data member is assigned with the removed node’s single child.
Case 3:The node being removed has two children. The node’s key is replaced by the successor’s key, and then the successor (which will fall under either Case 1 or Case 2) is removed. The successor is the next largest node in the tree, and is always the right child’s leftmost child.
