Balancing Trees
Height balanced: Difference in height of subtrees for every node is 0 or 1
Perfectly Balanced: Height balanced and all leaves are on 1, max 2 levels
Height: Number of “levels” or nodes under a specific node
Calculations:
Number of nodes on a level: 2h-1
Where h is the level you want to check
Number of nodes on all levels for a specified tree height: n = 2h – 1
Where h is the height of the tree
Balancing Algorithm using an array then adding elements to tree:
void balance ( T data[ ], int first, int last )
{
if(first <= last) {
int middle = (first + last)/2;
insert(data[middle]);
balance(data, first, middle-1);
balance(data, middle+1, last);
}
}
Steps (Recursive):
1. Sort Data
2. Find Middle
3. Insert Middle element
4. Repeat (2) on left half
5. Repeat (2) on right half
Complexity: O(lg n)
- Eliminates half of search space with each iteration
- Better an linked list: O(n)
, DSW Algorithm
No external data structure as tree rotations are used
Rotations:
- Left rotation: Parent becomes left child of its right child
- Right rotation: Parent becomes right child of its left child
Parent
D
Left A E Right
Child Child
E A
D D
E
A
rotateRight ( Gr, par, Ch )
if Par is not the root of the tree //Gr!=null
grandparent Gr of child Ch becomes Ch’s parent;
right subtree of Ch becomes left subtree of Ch’s parent Par;
node Ch acquires Par as its right child;
Right rotation with leaf nodes attached:
- Parent becomes right child of left child
- Left child’s right branch becomes old parent’s left branch
Left rotation with leaf nodes attached:
- Parent becomes left child of right child
- Right child’s left branch becomes old parent’s right branch
Height balanced: Difference in height of subtrees for every node is 0 or 1
Perfectly Balanced: Height balanced and all leaves are on 1, max 2 levels
Height: Number of “levels” or nodes under a specific node
Calculations:
Number of nodes on a level: 2h-1
Where h is the level you want to check
Number of nodes on all levels for a specified tree height: n = 2h – 1
Where h is the height of the tree
Balancing Algorithm using an array then adding elements to tree:
void balance ( T data[ ], int first, int last )
{
if(first <= last) {
int middle = (first + last)/2;
insert(data[middle]);
balance(data, first, middle-1);
balance(data, middle+1, last);
}
}
Steps (Recursive):
1. Sort Data
2. Find Middle
3. Insert Middle element
4. Repeat (2) on left half
5. Repeat (2) on right half
Complexity: O(lg n)
- Eliminates half of search space with each iteration
- Better an linked list: O(n)
, DSW Algorithm
No external data structure as tree rotations are used
Rotations:
- Left rotation: Parent becomes left child of its right child
- Right rotation: Parent becomes right child of its left child
Parent
D
Left A E Right
Child Child
E A
D D
E
A
rotateRight ( Gr, par, Ch )
if Par is not the root of the tree //Gr!=null
grandparent Gr of child Ch becomes Ch’s parent;
right subtree of Ch becomes left subtree of Ch’s parent Par;
node Ch acquires Par as its right child;
Right rotation with leaf nodes attached:
- Parent becomes right child of left child
- Left child’s right branch becomes old parent’s left branch
Left rotation with leaf nodes attached:
- Parent becomes left child of right child
- Right child’s left branch becomes old parent’s right branch
