Mod 6 Flashcards
What is a common way to evaluate the balance of a Binary Search Tree?
A common way we can evaluate the balance of a BST is by height. A BST is height-balanced if, at every node in the tree, the heights of the node’s left and right subtrees differ by at most 1.
What metric can we use to determine if the subtree rooted at a node is height-balanced?
A BST node’s balance factor. he balance factor of a node N is the difference in height between N’s right subtree and its left subtree:
balanceFactor(N) = height(N.right) - height(N.left)
By convention, the height of a NULL node (i.e., an empty subtree) is −1.
Explain what left-heavy and right-heavy nodes in a BST are.
If a node has a negative balance factor (i.e., balanceFactor(N) < 0), we call it left-heavy, since a negative balance factor implies that the node’s left subtree has a greater height than its right subtree.
Similarly, a node with a positive balance factor (i.e., balanceFactor(N) > 0) is called right-heavy, since the node’s right subtree would have a greater height than its left subtree.
When does a left rotation occur in an AVL tree?
A left rotation, also known as an “R-R” rotation, occurs when there is an imbalance in the right child of the center, and an imbalance in that node’s right subtree. Therefore, the term R-R denotes that the node’s right child is right-heavy.
What are the four rotation cases and when do we use them?
- Single Right Rotation (L-L): used when the center is imbalanced (left heavy) and its left child is left heavy.
- Double Left-Right Rotation (L-R): used when the center is unbalanced (left heavy) and its left child is right heavy. Rotate left around C then right around N.
- Double Right Left Rotation (R-L): used when the center is unbalanced (right heavy) and its right child is left heavy. Rotate right around C then left around N.
- Single Left Rotation (R-R): used when the center is imbalanced (right heavy) and its right child is right heavy.
When is a single right rotation needed?
When the balance factor at a node is -2 and he balance factor of N’s left child C is −1 or 0.
What will happen in a right rotation?
- N will become the right child of its current left child C.
- C’s current right child will become N’s left child.
- If N has a parent PN, then C will replace N as PN’s child. Otherwise, if N was the root of the entire tree, C will replace N as the root.
What will happen in a left rotation?
- N will become the left child of its current right child C.
- C’s current left child will become N’s right child.
- If N has a parent PN, then C will replace N as PN’s child. Otherwise, if N was the root of the entire tree, C will replace N as the root.
What is the pseudocode to find an element with key kq in a bst?
find(bst, kq):
n ← bst.root
while n is not None:
if n.key equals kq:
return success
else if kq < n.key:
n ← n.left
else:
n ← n.right
return failure
What is the pseudocode to insert an element in a BST?
insert(bst, k, v):
p ← None
n ← bst.root
while n is not None:
p ← n
if k < n.key:
n ← n.left
else:
n ← n.right
create a new node as the child of p containing k, v
return p
what is pseudocode to remove an element in a BST?
remove(bst, k):
n, pn ← find the node to be removed and its parent
based on key k, as in the find() function
if n has no children:
update pn to point to None instead of n
else if n has only 1 child:
update pn to point to n’s child instead of n
else:
s, ps ← find n’s inorder successor and its
parent, as described above
s.left ← n.left
if s is not n.right:
ps.left ← s.right
s.right ← n.right
update pn to point to s instead of n
update s.parent to point to pn
return ps
What is the pseudocode for a left rotation?
rotateLeft(n):
c ← n.right
n.right ← c.left
if n.right is not NULL:
n.right.parent ← n
c.left ← n
n.parent ← c
updateHeight(n)
updateHeight(c)
return c
What is the pseudocode for a right rotation?
rotateRight(n):
c ← n.left
n.left ← c.right
if n.left is not NULL:
n.left.parent ← n
c.right ← n
n.parent ← c
updateHeight(n)
updateHeight(c)
return c
What is the pseudocode to update the height of a node? Assume that the node has a height property and that function MAX() returns the highest value of 2 integer parameters.
updateHeight(n):
n.height ← MAX(height(n.left), height(n.right)) + 1
What is the pseudocode for inserting a node into an avl tree?
avlInsert(tree, key, value):
insert key, value into tree like normal BST insertion
n ← newly inserted node
p ← n.parent
while p is not NULL:
rebalance(p)
p ← p.parent
