Balanced Trees - Chapter 6

Question 1

An blank is a BST with a height balance property and specific operations to rebalance the tree when a node is inserted or removed.

Answer 1

AVL tree

Question 2

A BST is blank if for any node, the heights of the node’s left and right subtrees differ by only 0 or 1.

Answer 2

height balanced

Question 3

A node’s blank is the left subtree height minus the right subtree height, which is 1, 0, or -1 in an AVL tree.

Answer 3

balance factor

Question 4

With the height stored as a member of each node, the balance factor for any node can be computed in blank time

Answer 4

O(1)

Question 5

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.

Answer 5

Adelson-Velsky and Landis,

Question 6

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.

Answer 6

rotation

Question 7

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.

Answer 7

rebalanced

Question 8

blank an item into an AVL tree may cause the tree to become unbalanced. A rotation can rebalance the tree.

Answer 8

Inserting

Question 9

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.

Answer 9

double rotation

Question 10

An AVL blank involves searching for the insert location, inserting the new node, updating balance factors, and rebalancing.

Answer 10

tree insertion

Question 11

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].

Answer 11

Insertion

Question 12

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
}
}

Answer 12

AVLTreeInsert algorithm

Question 13

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.

Answer 13

O(1)
O(log N)

Question 14

Because a fixed number of temporary pointers are needed for the AVL insertion algorithm, including any rotations, the space complexity is blank.

Answer 14

O(1)

Question 15

Given a key, an AVL tree blank removes the first-found matching node, restructuring the tree to preserve all AVL tree requirements.

Answer 15

remove operation

Question 16

Removal begins by removing the node using the blank.

Answer 16

standard BST removal algorithm

Question 17

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.

Answer 17

rebalanced

Question 18

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.

Answer 18

BSTSearch

Question 19

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.

Answer 19

O(1)
O(log N)

Question 20

Because a fixed number of temporary pointers are needed for the AVL removal algorithm, including any rotations, the space complexity is blank.

Answer 20

O(1)

Question 21

Because AVL Trees are a form of a blank, the AVLTree class is similar to the BinarySearchTree class.

Answer 21

binary search tree

Question 22

In an AVL tree, A Node class is used that contains data members key, left, and right, as well as two new data members:

Answer 22

parent
height

Question 23

blank - A pointer to the parent node, or None for the root.

Answer 23

parent

Question 24

blank - The height of the subtree at the node. A single node has a height of 0.

Answer 24

height

Question 25

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.

Answer 25

height
parent

Question 26

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.

Answer 26

get_balance()

Question 27

blank - Calculates the node’s current height and assigns the height data member with the new value.

Answer 27

update_height()

Question 28

blank - Assigns either the left or right child data members with a new node.

Answer 28

set_child()

Question 29

blank - Replaces a current child node with a new node.

Answer 29

replace_child()

Question 30

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

Answer 30

rotate_left() and rotate_right()

Question 31

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.

Answer 31

rebalance() method

Question 32

AVL insertions are performed in two steps:

Answer 32

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.

Question 33

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.

Answer 33

O(log n)

Question 34

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.

Answer 34

O(log n)
O(log n)
O(1)

Question 35

The insert() method has a worst-case runtime of blank

Answer 35

O(log n)

Question 36

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

Answer 36

The AVLTree insert() method

Question 37

Removal from an AVL tree is a two-step process, similar to insertion:

Answer 37

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.

Question 38

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.

Answer 38

O(1)

Question 39

Because the height of an AVL tree is guaranteed to be blank
, the entire remove algorithm runs in worst-case blank time.

Answer 39

O(log n)

Question 40

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

Answer 40

The AVLTree remove_node() method

Question 41

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.

Answer 41

in the tree

Question 42

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)

Answer 42

The search() and remove_key() methods

Question 43

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.

Answer 43

red-black tree

Question 44

The red-black tree’s requirements ensure that a tree with N nodes will have a height of blank

Answer 44

O(log N)

Question 45

In a red black tree, Every node is colored either blank or blank.

Answer 45

red or black

Question 46

In a red black tree, the root node is blank.

Answer 46

black

Question 47

In a red black tree, All paths from a node to any null leaf descendant node must have the same number of blank.

Answer 47

black nodes

Question 48

In a red black tree, A null child is considered to be a blank.

Answer 48

black leaf node

Question 49

in a red black tree, A red node’s children cannot be blank.

Answer 49

red

Question 50

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.

Answer 50

Rotations

Question 51

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.

Answer 51

left rotation

Question 52

A blank at a node causes the node’s left child to take the node’s place in the tree.

Answer 52

right rotation

Question 53

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.

Answer 53

RBTreeSetChild utility

Question 54

The blank utility function replaces a node’s left or right child pointer with a new value.

Answer 54

RBTreeReplaceChild

Question 55

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.

Answer 55

insert operation

Question 56

The red-black balance operation consists of the steps:

Answer 56

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.

Question 57

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.

Answer 57

remove operation

Question 58

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.

Answer 58

remove-key operation

Question 59

RBTreeRemoveNode() consists of the following steps:

Answer 59

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.

Question 60

Prepare-for-removal algorithm case descriptions -
Node is red or node’s parent is null.

Answer 60

None and stop

Question 61

Prepare-for-removal algorithm case descriptions -
Sibling node is red.

Answer 61

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

Question 62

Prepare-for-removal algorithm case descriptions -
Parent is black and both of sibling’s children are black.

Answer 62

Color sibling red and call removal preparation function on parent.

Stop

Question 63

Prepare-for-removal algorithm case descriptions -
Parent is red and both of sibling’s children are black.

Answer 63

Color parent black and sibling red.

Stop

Question 64

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.

Answer 64

Color sibling red and sibling’s left child black. Rotate right at sibling.

Proceed

Question 65

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.

Answer 65

Color sibling red and sibling’s right child black. Rotate left at sibling.

Proceed

Question 66

Preparation for removing a node first checks for each of the six cases, performing the operations

Answer 66

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.

Question 67

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:

Answer 67

parent
color

Question 68

blank - A pointer to the parent node, or None for the root.

Answer 68

parent

Question 69

blank- A string representing the node’s color, set to either “red” or “black”.

Answer 69

color

Question 70

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.

Answer 70

are_both_children_black()

Question 71

Returns the number of nodes in this subtree, including the node itself.

Answer 71

count()

Question 72

Returns this node’s grandparent, or None if this node has no grandparent.

Answer 72

get_grandparent()

Question 73

Returns the predecessor from this node’s left subtree.

Answer 73

get_predecessor()

Question 74

Returns this node’s sibling, which is the other child of this node’s parent. Returns None if this node has no sibling.

Answer 74

get_sibling()

Question 75

Returns this node’s uncle, which is the sibling of this node’s parent. Returns None if this node has no uncle.

Answer 75

get_uncle()

Question 76

Returns True if this node is black, False otherwise.

Answer 76

is_black()

Question 77

Returns True if this node is red, False otherwise.

Answer 77

is_red()

Question 78

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.

Answer 78

replace_child()

Question 79

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”.

Answer 79

set_child()

Question 80

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.

Answer 80

Tree rotations

Question 81

The RedBlackTree class contains 3 methods for insertion:

Answer 81

insert()
insert_node()
insertion_balance()

Question 82

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().

Answer 82

insert()

Question 83

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.

Answer 83

insert_node()

Question 84

Alters the tree as necessary to ensure red-black tree requirements are met after inserting a new node.

Answer 84

insertion_balance()