Lesson test: Keeping a tree balanced

Sign in

Libre University uses your GitHub account. Signing in is only needed to sit a final test, so the score is kept on your profile.

Keeping a tree balanced

1.[3p]
Why does a rotation preserve the binary search tree property?

The subtree that changes sides already lay between the two rotated keys in value

Correct

Because the keys are re-sorted afterwards

The answer is: The subtree that changes sides already lay between the two rotated keys in value

Because only leaves are moved

The answer is: The subtree that changes sides already lay between the two rotated keys in value

Because the heights of both subtrees are equal

The answer is: The subtree that changes sides already lay between the two rotated keys in value

2.[2p]
How many pointers does a single rotation have to change, regardless of subtree size?

CorrectNot quite: 3

3.[3p]
Inserting into an AVL node's left child's right subtree needs

a double rotation, left at the child then right at the node

Correct

a single right rotation at the node

The answer is: a double rotation, left at the child then right at the node

a single left rotation at the node

The answer is: a double rotation, left at the child then right at the node

a recolouring only

The answer is: a double rotation, left at the child then right at the node

4.[3p]
The fewest nodes in an AVL tree of height $h$ obey $N (h) = N (h - 1) + N (h - 2) + 1$ with $N (0) = 1$ and $N (1) = 2$ . What is $N (5)$ ?

CorrectNot quite: 20

5.[3p]
Using $h \leq 1.4405 \log_{2} (n + 2) - 0.3277$ , what is the AVL height bound for a million keys?

CorrectNot quite: 28.4

6.[2p]
A red-black tree gives a tighter height bound than an AVL tree.

True

The answer is: False

False

Correct

7.[3p]
Why do most standard libraries ship red-black trees rather than AVL trees?

Select all that apply

An insertion needs at most two rotations and a deletion at most three, both constants

Correct

Much of the repair is done by recolouring, which is cheaper than pointer surgery

Correct

AVL deletion can cascade rotations all the way to the root

Correct

Red-black trees are shorter, so lookups are faster

The answer is: An insertion needs at most two rotations and a deletion at most three, both constants, Much of the repair is done by recolouring, which is cheaper than pointer surgery, AVL deletion can cascade rotations all the way to the root

8.[3p]
A B-tree node holds about 1000 children. How many levels does it take to hold a billion keys?

CorrectNot quite: 3

9.[3p]
Match each structure to what distinguishes it.

AVL tree
Red-black tree
Treap
Splay tree

every path holds the same black count
subtree heights differ by at most one
a random priority kept in heap order
every accessed node rotated to the root

Show the answer

AVL tree: subtree heights differ by at most one Red-black tree: every path holds the same black count Treap: a random priority kept in heap order Splay tree: every accessed node rotated to the root

1.[3p] Why does a rotation preserve the binary search tree property?

2.[2p] How many pointers does a single rotation have to change, regardless of subtree size?

3.[3p] Inserting into an AVL node's left child's right subtree needs

4.[3p] The fewest nodes in an AVL tree of height h obey N(h)=N(h−1)+N(h−2)+1 with N(0)=1 and N(1)=2. What is N(5)?

5.[3p] Using h≤1.4405log2(n+2)−0.3277, what is the AVL height bound for a million keys?

6.[2p] A red-black tree gives a tighter height bound than an AVL tree.

7.[3p] Why do most standard libraries ship red-black trees rather than AVL trees?

8.[3p] A B-tree node holds about 1000 children. How many levels does it take to hold a billion keys?

9.[3p] Match each structure to what distinguishes it.

1.[3p]
Why does a rotation preserve the binary search tree property?

2.[2p]
How many pointers does a single rotation have to change, regardless of subtree size?

3.[3p]
Inserting into an AVL node's left child's right subtree needs

4.[3p]
The fewest nodes in an AVL tree of height $h$ obey $N (h) = N (h - 1) + N (h - 2) + 1$ with $N (0) = 1$ and $N (1) = 2$ . What is $N (5)$ ?

5.[3p]
Using $h \leq 1.4405 \log_{2} (n + 2) - 0.3277$ , what is the AVL height bound for a million keys?

6.[2p]
A red-black tree gives a tighter height bound than an AVL tree.

7.[3p]
Why do most standard libraries ship red-black trees rather than AVL trees?

8.[3p]
A B-tree node holds about 1000 children. How many levels does it take to hold a billion keys?

9.[3p]
Match each structure to what distinguishes it.