AVL Trees Flashcards Preview

COMP26120 - Algorithms > AVL Trees > Flashcards

Flashcards in AVL Trees Deck (5)
Loading flashcards...
1
Q

what is an AVL tree

A

A binary search tree with the height balance property.

Adds an extra retracing step after altering the tree

2
Q

what is the height of an AVL tree

A

O(log n)

where n is the number of nodes

3
Q

what is retracing

A

travel up from an updated node and perform rotations if balance factor becomes left heavy (-2) or right heavy (2)

4
Q

describe a left heavy tree and the action that should be taken

A

A is left of B
bf(B) = -2, bf(A) = 0 -> left right
bf (B) = -2, bf(A) = -1 -> right

5
Q

describe a right heavy tree and the action that should be taken

A

A is right child of B
bf(B)=2, bf(A)=0 -> right left
bf(B)=2, bf(A)=1 -> left