AVL Flashcards
What is the balance factor of a node?
The balance factor of a node describes how balanced the
subtree of that node is and, if it is not perfectly balanced,
which side of the subtree (left side or right side) is “heavier”.
How is balance factor calculated?
The balance factor of a node is calculated by subtracting the height of the left subtree by the height of the right subtree.
When is an AVL tree considered balanced?
A balance factor between -1 and 1 (inclusive) means that the subtree is considered balanced.
When does a Left Rotation happen?
A left rotation happens when you have a node whose balance factor is -2, and its right child has a balance factor of 0 or -1.
What happens in a left rotation?
The top node becomes the left
child of the middle node.
When does a Right Rotation happen?
A right rotation happens when you have a node whose balance factor is 2, and its left child has a balance factor of 0 or 1.
What happens in a right rotation?
When a right rotation happens, the top node becomes the right child of the middle node.
When does a Left - Right rotation happen?
It happens when you have a node whose balance factor is 2, and its left child has a balance factor of -1.
What happens in a Left - Right rotation?
When a left-right rotation happens, the top node becomes the right child of the bottom node, and the middle node becomes the left child of the bottom node.
When does a Right - Left rotation happen?
It happens when you have a node whose balance factor is -2, and its right child has a balance factor of 1.
What happens in a Right - Left rotation?
The top node becomes the
left child of the bottom node, and the middle node becomes the right child of the bottom node.
What is the average case Big O for inserting in an AVL?
O ( log n )
What is the average case Big O for searching in an AVL?
O ( log n )
What is the average case Big O for deleting in an AVL?
O ( log n )
What is the worst case Big O for inserting in an AVL?
O ( log n )
