AVL Tree (Module 8.3)

Question 1

What determines the cost of lookup?

Answer 1

how far down the tree needs to go

Question 2

The number of nodes on the longest path from the root to a leaf is the ______ of the tree.

Answer 2

height

Question 3

The lookup for a tree of height h has ALWAYS which complexity?

Answer 3

O(h)

Question 4

A tree is balanced if ________, where h is its height and n is the number of nodes.

Answer 4

h - O(log n)

Question 5

What are the 3 requirements for balanced trees?

Answer 5

1) the tree is a BST
2) all paths from the root to a leaf have height either h or h-1
3) the leaves at height h be on the left-hand side of the tree

Question 6

Trees that remain balanced as inserting new nodes and continue to be a valid BST is known as?

Answer 6

self-balancing

Question 7

What is it called when at every node, the heights of the left and right subtrees differ by at most 1?

Answer 7

height invariant

Question 8

What is used when an imbalance occurs in a straight-line pattern?

Answer 8

Single Rotation

Question 9

Which type of rotation occurs when a node is inserted into the left subtree of the left child?

Answer 9

LL (Left-Left) Rotation

Question 10

Which type of rotation is performed on an unbalanced node for LL Rotation?

Answer 10

Right rotation

Question 11

Which type of rotation occurs when a node is inserted into the right subtree of the right child?

Answer 11

RR (Right-Right) Rotation

Question 12

Which type of rotation is performed on the unbalanced node for RR Rotation?

Answer 12

Left rotation