Description
1. Introduction
Today you will be turning a regular Binary Search Tree into a Balanced Binary Search Tree. Don’t worry about having to implement the BSTree class all over again, this time we have provided you with a working implementation. All you have to do is modify the `insert` method to allow for balanced insertions. However, depending on your implementation, you may choose to add additional methods, class data members, or helper functions to accomplish a balanced insertion. First we will go over what it means for a BST to be balanced, then some different implementations for balancing, and finally the starter code.
2.0 Balanced Binary Search Trees
Why do we need to balance?
Binary search trees are a nice idea, but they fail to accomplish our goal of doing lookup, insertion and deletion each in time O(log2(n)), when there are n items in the tree. Imagine starting with an empty tree and inserting 1, 2, 3 and 4, in that order.
1 1 1 1
\ \ \
2 2 2
\ \
3 3
\
4
You do not get a branching tree, but a linear tree. All of the left subtrees are empty. Because of this behavior, in the worst case each of the operations (lookup, insertion and deletion) takes time Θ(n). From the perspective of the worst case, we might as well be using a linked list and linear search.
> [Source](www.cs.ecu.edu/karl/3300/spr16/Notes/DataStructure/Tree/balance.html)
Balancing
When to balance a BST is generally based on the height of it’s sub-trees. A node will be unbalanced if the heights of its sub-trees differ by more than 1. A tree will be *height-balanced* if all of its nodes are balanced.
**Example of unbalanced tree:**
Notice how the node with value `76` in the right sub-tree has a left sub-tree of height 3, but a right sub-tree of height 0. Notice the same discrepancy in the left sub-tree at node with value `9`. Both of these problems are grounds for balancing.
**Example of tree after balancing:**
Notice the heights of the sub-trees in the balanced version above, they only ever differ by 1, thus they pass our height requirement. Also notice the differing arrangment of nodes: the node with value `12` is now the parent of nodes `9` and `14`, the node with value `72` is now the parent of nodes `54` and `76`. We performed swaps on nodes based on their values and the heights of sub-trees.
Rotations
We’ve seen why we need to Balance Binary Search Trees, when to balance them, and what an unbalanced tree versus a balanced tree looks like, but how do we perform the swaps necessary to achieve the correct result?
In the examples above, the trees were balanced by using rotations. If the height of a left sub-tree is greater than or equal to the height of the right sub-tree plus 2, then we perform a right rotation. Inversely, if the height of a right sub-tree is greater than or equal to the height of the left sub-tree plus 2, then we perform a left rotation.
Heights of left sub-tree = L and right sub-tree = R
If L >= (R + 2) then rotate right.
If R >= (L + 2) then rotate left.
**Example of Rotate Left Function**
“`C++
BST_Tree::BST_Node* BST_Tree::rotateLeft(BST_Tree::BST_Node* node){
BST_Node* p = node->right;
node->right = node->right->left;
p->left = node;
return p;
}
“`
The above `rotateLeft` method would turn this tree:
In to this tree:
3.0 Red-Black Trees
**Definition of a red-black tree**
A red-black tree is a binary search tree which has the following red-black properties:
<ul>
<li>Every node is either red or black.</li>
<li>Every leaf (NULL) is black.</li>
<li>If a node is red, then both its children are black.</li>
<li>Every simple path from a node to a descendant leaf contains the same number of black nodes.</li>
</ul>
> [Source](https://www.cs.auckland.ac.nz/software/AlgAnim/red_black.html)
Insert Operation
The goal of the insert operation is to insert key K into tree T, maintaining T’s red-black tree properties. A special case is required for an empty tree. If T is empty, replace it with a single black node containing K. This ensures that the root property is satisfied.
If T is a non-empty tree, then we do the following:
<ol>
<li>use the BST insert algorithm to add K to the tree</li>
<li>color the node containing K red</li>
<li>restore red-black tree properties (if necessary)</li>
</ol>
> [Source](http://pages.cs.wisc.edu/~paton/readings/Red-Black-Trees/)
4.0 Starter Code
The starter code consists of BST_Tree.h (BST_Tree class definition), BST_Tree.cpp (a working implementation of a BST), and a GUI you can use to visualize your work.
# 4.1 Class Contents
In BST_Tree:
* A struct, BST_Node which contains:
+ An integer for storing the node’s data
+ A BST_Node* which points to a node’s left child
+ A BST_Node* which points to a node’s right child
+ A base constructor which sets the node’s value to 0 and left and right pointer’s to null
+ A constructor which sets a given int parameter to the node’s value
+ A constructor which takes a reference to a node, called other, and sets the node’s value to other’s value, then sets left and right pointers to null
* A BST_Node* which points to the root of the BST_Tree
* A constructor which sets the root pointer to null
* An `insert` method which will need to be reworked to allow for balanced insertion
* A `clear` method which deletes the root node and sets the pointer to null
* A `getRoot` method which returns the root node of the BST_Tree
5.0 Task
As we have mentioned at length above, the purpose of this lab is to modify the existing insert method to allow for balanced insertions. It is up to you as to how to do this.
For example, you could use a red-black tree insertion algorithm, a 2-3 tree insertion algorithm, or simply attempt to balance the BST using rotations.
Regardless of what algorithm you choose to implement, you will very likely need to implement helper methods such as `rotateRight`(rotates nodes from left to right), `rotateLeft`(rotates nodes from right to left), and `height`(returns the height of a tree or subtree).
If you choose to implement a red-black tree insertion algorithm, you will need to add a char variable to the BST_Node struct within the BST_Tree class representing node color (I.E. ‘r’ for red and ‘b’ for black). You will also need a method `changeColor` to change the color of nodes when necessary.
6.0 Submission
You will submit BST_Tree.h and BST_Tree.cpp after modifying the insertion method to create a balanced tree.
As always it is highly recommended to work in groups and utilize online TA hours.
