avl trees Flashcards
1
Q
additional properties
A
bst with additional properties:
- every node is balanced in avl terms
+++height of left and right subtree are at most different by 1
2
Q
ad and disadvantages
A
\++ = balanced tree in worst case -- = more work adding and removing nodes
3
Q
the height at each node is precalculated and stored - usually as an instance variable in the node
A
true
4
Q
balance algorithm
A
see notes - better understand than memorize
5
Q
complexity analysis
A
worst case - all operations are O(log n)
