AVL Tree (Balanced BST)

0.0(0)
studied byStudied by 0 people
0.0(0)
full-widthCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/8

encourage image

There's no tags or description

Looks like no tags are added yet.

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

9 Terms

1
New cards

O(log n)

AVL height is ____

2
New cards

bf(x)

balance factor is

3
New cards

height(left subtree) - height(right subtree)

bf(x) = ____ - ______

4
New cards

h <= 1.4405 log n + O(1)

height theorem is ______

5
New cards

O(log n)

Find/Query is in ____ time

6
New cards

O(log n)

Insert/Delete is in ____ time

7
New cards

rotation

Balancing mechanism is _____ (left and right)

8
New cards

bf = 2/-2

if AVL property violated ______ perform rotation

9
New cards

  1. left-left

  2. right-right

  3. left-right

  4. right-left

violation cases:
1. (single)
2. (single)
3. (double)
4. (double)