The keys 1, 2, 3, …, 1000 are inserted in this order into a plain (non-balancing) BST. What is the height of the resulting tree (a single node has height 0)?
In an AVL tree, which balance factors may a node have once an operation has finished?
What does this program print? (It uses the chapter's convention: empty tree −1, leaf 0.)
public class HeightDemo {
static class Node {
int key; Node left, right;
Node(int key) { this.key = key; }
}
static int height(Node n) {
return n == null ? -1 : 1 + Math.max(height(n.left), height(n.right));
}
static int bf(Node n) {
return height(n.left) - height(n.right);
}
public static void main(String[] args) {
Node a = new Node(10);
a.left = new Node(5);
a.left.left = new Node(2);
a.right = new Node(20);
System.out.println(height(a) + " " + bf(a) + " " + bf(a.left));
}
}
What is the time complexity of a single rotation in an AVL tree with n nodes?
The keys 30, 20, 10 are inserted in this order into an empty AVL tree. Which repair is performed?
The keys 50, 20, 40 are inserted in this order into an empty AVL tree. Which key is the root afterwards, and which case occurred?
The keys 20, 60, 40 are inserted in this order into an empty AVL tree. What is the pre-order traversal of the result?
The keys 10, 20, 30, 40, 50 are inserted in this order into an empty AVL tree. What is the pre-order traversal of the final tree?
The keys 1, 2, 3, 4, 5, 6, 7 are inserted in this order into an empty AVL tree. Which statement about the final tree is true?
The keys 40, 20, 60, 10, 30, 25 are inserted in this order into an empty AVL tree. What is the pre-order traversal of the final tree?
The keys 10, 20, 30, 25, 28, 27 are inserted in this order into an empty AVL tree. Which sequence of repairs is performed (listing the case and the unbalanced node)?
The keys 30, 10, 50, 5, 20, 40, 60, 15, 25 have been inserted into an AVL tree without any rotation. Now 22 is inserted. What is the lowest unbalanced node, and which case is it?
A right rotation is applied at node z, whose left child is y. The subtrees are named as in the diagram (T1, T2 under y's left child x; T3 = y's right subtree; T4 = z's right subtree). Which subtree gets a new parent?
Why does AVL insertion perform at most one single or double rotation, even though it walks all the way back to the root?
A student implements AVL insertion but writes rotateRight(n.left); instead of n.left = rotateRight(n.left);. What is the most likely effect?
What is the minimum number of nodes an AVL tree of height 4 can have (a single node has height 0)?
What is the greatest possible height of an AVL tree that holds exactly 15 keys?
An AVL tree stores 1,000,000 distinct keys. About how many nodes does an unsuccessful search visit, at most?
Which Java collection is backed by a self-balancing binary search tree, and which kind?
Which statement correctly compares AVL trees with red-black trees?
Does this class compile?
public class AVLTree<K> {
private static class Node<K> {
K key; Node<K> left, right; int height;
Node(K key) { this.key = key; }
}
private Node<K> root;
public boolean contains(K key) {
Node<K> cur = root;
while (cur != null) {
int c = key.compareTo(cur.key);
if (c == 0) return true;
cur = c < 0 ? cur.left : cur.right;
}
return false;
}
}
In the LR case at z (left child y, y's right child x, with x's subtrees T2 and T3), a double rotation is performed. Where do T2 and T3 end up?
The keys 8, 5, 11, 3, 7, 10, 12, 2, 4, 6, 9, 1 are inserted into an empty AVL tree (no rotations happen: it is a minimum-size tree of height 4). Then 12 is deleted. How many rebalancing operations (single or double rotations) does the deletion trigger?
The keys 40, 20, 60, 50, 70 are inserted into an empty AVL tree (no rotations), and then 20 is deleted. What is the pre-order traversal afterwards?
The keys 20, 10, 30, 5, 15, 25, 3 are inserted into an empty AVL tree (no rotations), and then 25 is deleted. What is the root afterwards?
Explain why the height of an AVL tree with n nodes is O(log n). Your answer should mention the minimum-size trees.
The keys 50, 20, 40 are inserted into an empty AVL tree. A student tries to repair the imbalance with a single right rotation at 50. Draw (or describe) the result and explain why a double rotation is needed.
Insertion into an AVL tree performs at most one single or double rotation, but deletion may perform rotations at many levels. Explain the difference.
Java's TreeMap guarantees O(log n) for get, put and remove. Which data structure makes this possible, and why could a plain binary search tree not give the same guarantee?
Given the node class below (no stored heights), write public static boolean isAVL(Node root) that returns true exactly when the tree is a valid AVL tree: a BST with distinct keys and |bf| ≤ 1 at every node. Your method must run in O(n) time.
static class Node {
int key; Node left, right;
Node(int k) { key = k; }
}
Write two static methods:
long minNodes(int h)— the fewest nodes an AVL tree of height h can have (height of an empty tree is −1, sominNodes(-1) == 0andminNodes(0) == 1). Use memoisation so thatminNodes(90)returns instantly.int maxHeight(long n)— the greatest height an AVL tree with n ≥ 1 nodes can have.
For example minNodes(4) is 12, maxHeight(15) is 4 and maxHeight(1000000) is 27.