AVL Trees: Balancing and Rotations

Balancing Trees Overview

• Balancing aims to maintain the properties of binary search trees
• Insertion into balancing trees automatically rearranges the tree to maintain a balance
• Three balancing trees include: AVL Trees, 2-4 Trees, and Red-Black Trees
• Balanced search trees help maintain a time complexity of O(log n)

AVL Trees

• AVL Trees calculate a "balance factor" for each node
• Rotations are performed based on insertions or tree modifications
• Rotations are done to update the trees balance factor
• Reference material for visualization of AVL Trees: AVL Tree Notes (slide 110) from Abdul Bari Notes

Balance Factors & Rotations

• Every node has a “balance factor” that is calculated as: balancing factor = hL - hR
• “hL” represents the height of the left subtree and “hR” represents the height of the right subtree.
• AVL Tree rebalances itself (performs a rotation) when a node's balance factor is outside of the inclusive range from [-1, 1]
• Common rotation types include: Single Left(SL), Single Right(SR), Double Left/Right(DL/RL) , Double Right/Left(DR/LR)

Tree Rotations

• Tree rotations can be visualized like strings pulling the unbalanced tree in a direction and the nodes following
• Rebalancing occurs as nodes are inserted
• Rebalancing occurs is an operation on a tree that has only just become unbalanced

Single Left (SL) Rotations

• After inserting a node and seeing a balance factor that is outside of the range [-1,1], the tree moves downward to the right
• A Single Left Rotation is performed on the tree and a balanced state is achieved
• The unbalanced node is observed and the string is pulled downward to the left of the unbalanced node

Single Right (SR) Rotations

• A balance factor that is outside of the range [-1,1] is observed
• Because the tree moves downward to the left, a single right rotation on the tree is performed
• To perform this rotation, the unbalanced node (C) is looked at, and the string is pulled downward and to the right of C

Double Rotations

• Two single rotations are performed
• One single rotation moves the node to the point where another rotation can be performed
• The final rotation balances the tree.

Double Left (Right Left) Rotations

• On the unbalanced node (A) the tree moves downward to the right, and then down to the left
• This action results in a double left rotation, or a right rotation that is followed by a single left rotation.
• Imagine “nailing” the string between A and C, A will not move
• If we pull a string that is over B and C to the right and downward, B will follow upward to C, and C will move to the right and down.

Double Right (Left Right)

• On the unbalanced node (C) the tree moves down to the left, and from there, down to the right
• This action results in a double right rotation, or a left rotation followed by a single right rotation
• Imagine nailing the string between C and A, and it will not move
• If the string is pulled over A and B to the left and downward, then B will follow upward to A, and A will move to the left and down

Building AVL Trees

• An extremely important concept to understand is building an AVL tree with given values ​​and performing balances as necessary.
• Given n input values in a specific order to be inserted, one must construct the tree and balance whenever necessary
• When visually or definitionally understanding what rotations are done, one needs to know how to recognize them as they're happening.
• AVL Tree Insertion (slide 118)

2-4 Trees Main Properties

• A 2-4 tree has multiple nodes possessing up to 3 elements
• If a node has 1 element, it is considered a 2-node
  • If internal, a 2-node has two children nodes
• If a node has 2 elements, it is considered a 3-node.
  • If internal, a 3-node has three children nodes.
• If a node has 3 elements, it is considered a 4-node
  • If internal, a 4-node has four children nodes
• All external (leaf) nodes possess the same depth

2-4 Tree Construction

• Insertion results in elements being placed in the same node
• To construct a tree with the following elements in order: 11, 14, 19, 25, 1, 3, 5, 18, 7, 96

2-4 Insertion & Overflow

• You can only have a maximum of three elements
• Inserting a fourth element is an overflow.
• To deal with an overflow, promote the third and split the sides
  • The first and second element moves to a new tree to the bottom left
  • The third element will be promoted and become the new root of the tree
  • The fourth element move to the a new node to the bottom right
• The process of insertion is continued on the bottom level

2-4 Tree Examples

• Following a series of performed “promotions” in order to make sense of the current 2-4 tree, you can evaluate as follows:
  • Evaluate values in reference to each other by the parent element's value:
    • Values 1, 3 which are <5
    • Values 7 between 5-11
    • Values 14, 18 between 11-19
    • Values 25 which are >19

Red Black Trees Rules

• The root is always black
• No red node has a child/parent that is also red
• The path from the root to any black leaf node should be the same for all paths to any given black leaf node
  • Can be found using the "black height" of a tree

Black Height

• Black height is the total number of black nodes on any given path from the root to a black leaf node, this includes the root and leaf.
• Compare this value of nodes to any other path to a black leaf node, you should also find the same number.
• This will validate the third condition of the red black tree

Red Black Trees Construction Cases

• When inserting a node, it is always inserted as red
• Three cases include:
  • Recoloring
  • Double Rotation
  • Single Rotation & Recolor

Red Black Trees Recolor Case

• When inserting a node with an initially red parent and the sibling node is also a red:
  • The siblings are red
  • Swap the colors of the siblings and their parent

Red Black Trees Double Rotation Case

• If inserting a node and it has a red parent and a black sibling (or null in this case)
  • Perform a single left or single right rotation (which turns it into a Case 3)
  • Perform another rotation to balance the tree (you will see this is Case 3)
  • Update the new root as black

Red Black Trees Recolor Case

• If the tree has a red parent:
  • Rotate the tree by performing a single left or single right rotation (depending on the case)
  • Properly recolor the tree (C1)

Red Black Trees: Constructing

• The number of comparisons building a red-black tree with n items is O(nlog(n))

Time Complexities

• Search has a Big O of O(log n)
  • Time complexity of finding a max / min value is O(log n)
• Insertion to first insert a node, one must know where to position the node, which requires a O(log n) search operation, and then can place the node
  • Overall, it is an O(log n) operation in itself
  • To insert n elements, it would be O(n log n) as for nodes one must search (log n) for where to put those nodes, and then place them
• Deletion:
  • Similar to insertion, deleting a node requires finding it, and has a Big O of O(log n).

Big O Extra Notes

• Make these make intuitive sense to you.
• The differing types of balancing trees have pros and cons - insertion and deletion complexity may vary slightly.
• AVL trees will likely use a lot of operations to maintain balance.
• red-black tree, may not be as balanced, uses less operations to maintain structure.