Balanced Trees - Chapter 6 Flashcards
An blank is a BST with a height balance property and specific operations to rebalance the tree when a node is inserted or removed.
AVL tree
A BST is blank if for any node, the heights of the node’s left and right subtrees differ by only 0 or 1.
height balanced
A node’s blank is the left subtree height minus the right subtree height, which is 1, 0, or -1 in an AVL tree.
balance factor
With the height stored as a member of each node, the balance factor for any node can be computed in blank time
O(1)
AVL is named for inventors blank and blank who described the data structure in a 1962 paper: “An Algorithm for the Organization of Information”, often cited as the first balanced tree structure.
Adelson-Velsky and Landis,
Inserting an item into an AVL tree may require rearranging the tree to maintain height balance. A blank is a local rearrangement of a BST that maintains the BST ordering property while rebalancing the tree.
rotation
When an AVL tree node has a balance factor of 2 or -2, which only occurs after an insertion or removal, the node must be blank via rotations.
rebalanced
blank an item into an AVL tree may cause the tree to become unbalanced. A rotation can rebalance the tree.
Inserting
Sometimes, the imbalance is due to an insertion on the inside of a subtree, rather than on the outside as above. One rotation won’t rebalance. A blank is needed.
double rotation
An AVL blank involves searching for the insert location, inserting the new node, updating balance factors, and rebalancing.
tree insertion
Blank starts with the standard BST insertion algorithm. After inserting a node, all ancestors of the inserted node, from the parent up to the root, are rebalanced. A node is rebalanced by first computing the node’s balance factor, then performing rotations if the balance factor is outside of the range [-1,1].
Insertion
AVLTreeInsert(tree, node) {
if (tree⇢root == null) {
tree⇢root = node
node⇢parent = null
return
}
cur = tree⇢root
while (cur != null) {
if (node⇢key < cur⇢key) {
if (cur⇢left == null) {
cur⇢left = node
node⇢parent = cur
cur = null
}
else {
cur = cur⇢left
}
}
else {
if (cur⇢right == null) {
cur⇢right = node
node⇢parent = cur
cur = null
}
else
cur = cur⇢right
}
}
node = node⇢parent
while (node != null) {
AVLTreeRebalance(tree, node)
node = node⇢parent
}
}
AVLTreeInsert algorithm
The AVL insertion algorithm traverses the tree from the root to a leaf node to find the insertion point, then traverses back up to the root to rebalance. One node is visited per level, and at most 2 rotations are needed for a single node. Each rotation is an blank operation. Therefore, the runtime complexity of insertion is blank.
O(1)
O(log N)
Because a fixed number of temporary pointers are needed for the AVL insertion algorithm, including any rotations, the space complexity is blank.
O(1)
Given a key, an AVL tree blank removes the first-found matching node, restructuring the tree to preserve all AVL tree requirements.
remove operation
Removal begins by removing the node using the blank.
standard BST removal algorithm
After removing a node, all ancestors of the removed node, from the nodes’ parent up to the root, are blank. A node is rebalanced by first computing the node’s balance factor, then performing rotations if the balance factor is 2 or -2.
rebalanced
To remove a key, the AVL tree removal algorithm first locates the node containing the key using blank. If the node is found, AVLTreeRemoveNode is called to remove the node. Standard BST removal logic is used to remove the node from the tree. Then AVLTreeRebalance is called for all ancestors of the removed node, from the parent up to the root.
BSTSearch
In the worst case scenario, the AVL removal algorithm traverses the tree from the root to the lowest level to find the node to remove, then traverses back up to the root to rebalance. One node is visited per level, and at most 2 rotations are needed for a single node. Each rotation is an blank operation. Therefore, the runtime complexity of an AVL tree removal is blank.
O(1)
O(log N)
Because a fixed number of temporary pointers are needed for the AVL removal algorithm, including any rotations, the space complexity is blank.
O(1)
Because AVL Trees are a form of a blank, the AVLTree class is similar to the BinarySearchTree class.
binary search tree
In an AVL tree, A Node class is used that contains data members key, left, and right, as well as two new data members:
parent
height
blank - A pointer to the parent node, or None for the root.
parent
blank - The height of the subtree at the node. A single node has a height of 0.
height
The blank data member is used to detect imbalances in the tree after insertions or removals, while the blank data member is used during rotations to correct imbalances.
height
parent
blank - Returns the node’s balance factor. The balance factor is the left child’s height minus the right child’s height. A height of -1 is used in the calculation if the child is None.
get_balance()
blank - Calculates the node’s current height and assigns the height data member with the new value.
update_height()
blank - Assigns either the left or right child data members with a new node.
set_child()
blank - Replaces a current child node with a new node.
replace_child()
Tree rotations are required to correct any problems where the left and right subtrees of a node have heights that differ by more than 1. After a new node is inserted into an AVL tree, either one or two rotations will fix any imbalance that happens. The blank and blank methods perform these operations
rotate_left() and rotate_right()
The blank examines the structure of the subtree of a node, and determines which rotations to do if a height imbalance exists at the node.
rebalance() method
AVL insertions are performed in two steps:
Insert into the tree using the normal binary search tree insertion algorithm.
Call rebalance() on all nodes along a path from the new node’s parent up to the root.
Insert into the tree using the normal binary search tree insertion algorithm requires blank
steps, since an AVL tree has blank
levels, and the loop makes the current node go down one level with each iteration.
O(log n)
Call rebalance() on all nodes along a path from the new node’s parent up to the root. requires blank
steps, again since the path back up to the root has blank
levels to visit, and rotations are blank
operations.
O(log n)
O(log n)
O(1)
The insert() method has a worst-case runtime of blank
O(log n)
def insert(self, node):
# Special case: if the tree is empty, just set the root to
# the new node.
if self.root is None:
self.root = node
node.parent = None
else:
# Step 1 - do a regular binary search tree insert.
current_node = self.root
while current_node is not None:
# Choose to go left or right
if node.key < current_node.key:
# Go left. If left child is None, insert the new
# node here.
if current_node.left is None:
current_node.left = node
node.parent = current_node
current_node = None
else:
# Go left and do the loop again.
current_node = current_node.left
else:
# Go right. If the right child is None, insert the
# new node here.
if current_node.right is None:
current_node.right = node
node.parent = current_node
current_node = None
else:
# Go right and do the loop again.
current_node = current_node.right
# Step 2 - Rebalance along a path from the new node's parent up
# to the root.
node = node.parent
while node is not None:
self.rebalance(node)
node = node.parent
The AVLTree insert() method
Removal from an AVL tree is a two-step process, similar to insertion:
Remove the node in the same way nodes are removed from a binary search tree. One of four cases is identified to determine how to remove the node. In the most general case, the node’s key is replaced by the successor node’s key in the tree, and the successor is then more easily removed.
Call rebalance() on all the nodes on the path from the removed node’s parent up to the root. If the node’s successor was ultimately removed, the rebalancing begins from the successor’s parent, not the original target node.
As with insertion, in AVT removal each step requires blank
operations to be performed, first on a path from the root down to a leaf, and then on a path near a leaf back up to the root.
O(1)
Because the height of an AVL tree is guaranteed to be blank
, the entire remove algorithm runs in worst-case blank time.
O(log n)
def remove_node(self, node):
# Base case:
if node is None:
return False
# Parent needed for rebalancing.
parent = node.parent
# Case 1: Internal node with 2 children
if node.left is not None and node.right is not None:
# Find successor
successor_node = node.right
while successor_node.left != None:
successor_node = successor_node.left
# Copy the value from the node
node.key = successor_node.key
# Recursively remove successor
self.remove_node(successor_node)
# Nothing left to do since the recursive call will have rebalanced
return True
# Case 2: Root node (with 1 or 0 children)
elif node is self.root:
if node.left is not None:
self.root = node.left
else:
self.root = node.right
if self.root is not None:
self.root.parent = None
return True
# Case 3: Internal with left child only
elif node.left is not None:
parent.replace_child(node, node.left)
# Case 4: Internal with right child only OR leaf
else:
parent.replace_child(node, node.right)
# node is gone. Anything that was below node that has persisted is already correctly
# balanced, but ancestors of node may need rebalancing.
node = parent
while node is not None:
self.rebalance(node)
node = node.parent
return True
The AVLTree remove_node() method
Often the user does not know where the desired node object to be removed is blank, or even if the node exists at all. The remove_key() method can be used to first search for the node using the BinarySearchTree search() method, and then call remove_node() only if search()returns a Node pointer.
in the tree
binary search tree search operation. Returns the node with the
Searches for a node with a matching key. Does a regular
# matching key if it exists in the tree, or None if there is no
# matching key in the tree.
def search(self, key):
current_node = self.root
while current_node is not None:
# Compare the current node’s key with the target key.
# If it is a match, return the current key; otherwise go
# either to the left or right, depending on whether the
# current node’s key is smaller or larger than the target key.
if current_node.key == key: return current_node
elif current_node.key < key: current_node = current_node.right
else: current_node = current_node.left
Attempts to remove a node with a matching key. If no node has a matching key
# then nothing is done and False is returned; otherwise the node is removed and
# True is returned.
def remove_key(self, key):
node = self.search(key)
if node is None:
return False
else:
return self.remove_node(node)
The search() and remove_key() methods
A blank is a BST with two node types, namely red and black, and supporting operations that ensure the tree is balanced when a node is inserted or removed.
red-black tree
The red-black tree’s requirements ensure that a tree with N nodes will have a height of blank
O(log N)
In a red black tree, Every node is colored either blank or blank.
red or black
In a red black tree, the root node is blank.
black
In a red black tree, All paths from a node to any null leaf descendant node must have the same number of blank.
black nodes
In a red black tree, A null child is considered to be a blank.
black leaf node
in a red black tree, A red node’s children cannot be blank.
red
A rotation is a local rearrangement of a BST that maintains the BST ordering property while rebalancing the tree. blank are used during the insert and remove operations on a red-black tree to ensure that red-black tree requirements hold.
Rotations
Rotating is said to be done “at” a node. A blank at a node causes the node’s right child to take the node’s place in the tree.
left rotation
A blank at a node causes the node’s left child to take the node’s place in the tree.
right rotation
The blank function sets a node’s left child, if the whichChild parameter is “left”, or right child, if the whichChild parameter is “right”, and updates the child’s parent pointer.
RBTreeSetChild utility
The blank utility function replaces a node’s left or right child pointer with a new value.
RBTreeReplaceChild
Given a new node, a red-black tree blank inserts the new node in the proper location such that all red-black tree requirements still hold after the insertion completes.
insert operation
The red-black balance operation consists of the steps:
Assign parent with node’s parent, uncle with node’s uncle, which is a sibling of parent, and grandparent with node’s grandparent.
If node is the tree’s root, then color node black and return.
If parent is black, then return without any alterations.
If parent and uncle are both red, then color parent and uncle black, color grandparent red, recursively balance grandparent, then return.
If node is parent’s right child and parent is grandparent’s left child, then rotate left at parent, assign node with parent, assign parent with node’s parent, and go to step 7.
If node is parent’s left child and parent is grandparent’s right child, then rotate right at parent, assign node with parent, assign parent with node’s parent, and go to step 7.
Color parent black and grandparent red.
If node is parent’s left child, then rotate right at grandparent, otherwise rotate left at grandparent.
Given a key, a red-black tree blank removes the first-found matching node, restructuring the tree to preserve all red-black tree requirements. First, the node to remove is found using BSTSearch. If the node is found, RBTreeRemoveNode is called to remove the node.
remove operation
Given a key, a red-black tree blank removes the key from the tree, if present, restructuring as needed to preserve all red-black tree requirements. First, BSTSearch() is called to find the node containing the key. If the node is found, RBTreeRemoveNode() is called to remove the node.
remove-key operation
RBTreeRemoveNode() consists of the following steps:
If the node has two children, copy the key from the node’s predecessor to a temporary value, recursively remove the predecessor from the tree, replace the node’s key with the temporary value, and return.
If the node is black, call RBTreePrepareForRemoval() to restructure the tree in preparation for the node’s removal.
Remove the node using the standard BST removal algorithm.
Prepare-for-removal algorithm case descriptions -
Node is red or node’s parent is null.
None and stop
Prepare-for-removal algorithm case descriptions -
Sibling node is red.
Color parent red and sibling black. If node is left child of parent, rotate left at parent node, otherwise rotate right at parent node.
Proceed
Prepare-for-removal algorithm case descriptions -
Parent is black and both of sibling’s children are black.
Color sibling red and call removal preparation function on parent.
Stop
Prepare-for-removal algorithm case descriptions -
Parent is red and both of sibling’s children are black.
Color parent black and sibling red.
Stop
Prepare-for-removal algorithm case descriptions -
Sibling’s left child is red, sibling’s right child is black, and node is left child of parent.
Color sibling red and sibling’s left child black. Rotate right at sibling.
Proceed
Prepare-for-removal algorithm case descriptions -
Sibling’s left child is black, sibling’s right child is red, and node is right child of parent.
Color sibling red and sibling’s right child black. Rotate left at sibling.
Proceed
Preparation for removing a node first checks for each of the six cases, performing the operations
1 If the node is red or the node’s parent is null, then return.
2 If the node has a red sibling, then color the parent red and the sibling black. If the node is the parent’s left child then rotate left at the parent, otherwise rotate right at the parent. Continue to the next step.
3 If the node’s parent is black and both children of the node’s sibling are black, then color the sibling red, recursively call on the node’s parent, and return.
4 If the node’s parent is red and both children of the node’s sibling are black, then color the parent black, color the sibling red, then return.
5 If the sibling’s left child is red, the sibling’s right child is black, and the node is the left child of the parent, then color the sibling red and the left child of the sibling black. Then rotate right at the sibling and continue to the next step.
6 If the sibling’s left child is black, the sibling’s right child is red, and the node is the right child of the parent, then color the sibling red and the right child of the sibling black. Then rotate left at the sibling and continue to the next step.
7 Color the sibling the same color as the parent and color the parent black.
8 If the node is the parent’s left child, then color the sibling’s right child black and rotate left at the parent. Otherwise color the sibling’s left child black and rotate right at the parent.
The RedBlackTree class is similar to the BinarySearchTree class because a red-black tree is a form of a binary search tree. The RBTNode class, representing red-black tree nodes, contains data members key, left, and right, as well as two new data members:
parent
color
blank - A pointer to the parent node, or None for the root.
parent
blank- A string representing the node’s color, set to either “red” or “black”.
color
Returns true if both child nodes are black. A child set to None is considered to be black, as per the red-black tree requirements.
are_both_children_black()
Returns the number of nodes in this subtree, including the node itself.
count()
Returns this node’s grandparent, or None if this node has no grandparent.
get_grandparent()
Returns the predecessor from this node’s left subtree.
get_predecessor()
Returns this node’s sibling, which is the other child of this node’s parent. Returns None if this node has no sibling.
get_sibling()
Returns this node’s uncle, which is the sibling of this node’s parent. Returns None if this node has no uncle.
get_uncle()
Returns True if this node is black, False otherwise.
is_black()
Returns True if this node is red, False otherwise.
is_red()
Replaces a current child node with a new node. Takes two RBTNode arguments: current_child and new_child, and if current_child is one of the node’s children, replaces current_child with new_child.
replace_child()
Assigns either the left or right child data members with a new node. Takes two arguments: which_child (string) and child (RBTNode), and sets child as the node’s left child if which_child is “left”, or sets child as the right child if which_child is “right”.
set_child()
Blank are required to help correct red-black tree requirement violations during an insertion or removal. The rotate_left() and rotate_right() RedBlackTree class methods perform left and right rotations, respectively.
Tree rotations
The RedBlackTree class contains 3 methods for insertion:
insert()
insert_node()
insertion_balance()
Blank - Takes a key as an argument, creates a new RBTNode containing the key, and then adds the node to the tree using insert_node().
insert()
blank - Takes a node as an argument, adds the node to the tree using standard BST insertion rules, and then calls insertion_balance() to balance the tree.
insert_node()
Alters the tree as necessary to ensure red-black tree requirements are met after inserting a new node.
insertion_balance()
