- Height of a node --> Depth of the subtree with said node as root
- (Number of layers below the node)
- Balance Factor of a node --> Difference between the left and right subtree depths
- Depth of left subtree - Depth of right subtree
- Height of left child - Height of right child
- Height of subtree is -1 if subtree is empty
- AVL Tree --> Binary Search Tree with all Balance Factors being either -1, 0, or 1
- Search implementation identical to BST
- s_i --> Minimum size of an AVL Tree of depth i
- See assignment
- Search
- Replacement of the BSTDictionary method
- RotateLeft
- Perform a left rotation at a node
- Private --> Can assume left rotations are always possible when this is called
- RotateRight
- Perform a right rotation at a node
- Private --> Can assume rightt rotations are always possible when this is called
- Change
- Replacement of the BSTDictionary method
- DeleteFromSubtree
- Replacement of the BSTDictionary method
- DeleteNode
- Replacement of the BSTDictionary method
- Successor
- Replacement of the BSTDictionary method