Create a balanced binary search tree. You will need to write a class named Rebal
ID: 3555012 • Letter: C
Question
Create a balanced binary search tree. You will need to write a class named RebalancingTree that extends the BST class given at the link listed below. You will also need to incorporate the AbstractTree class and the Tree interface, all of which can be downloaded from the following locations:
You should override the insert method in BST. Your overriding method should first call the method it is overriding. When 50 insertions have been performed since the last rebalancing, the tree should be examined to find the node with the highest balance factor. If there is more than one such node, always choose the one lowest on the tree. You should then rebalance the subtree rooted at that node. Your rebalancing should produce a balanced subtree.
Each time a rebalancing occurs, you should display the following information:
The average depth of the nodes is proportional to the average search time, so you should verify that it decreases after the rebalancing.
Your test method should create a balanced binary search tree of integers and then randomly generate 10,000 integers between 0 and 999 and insert them into the tree. After all the insertions are complete, use the inorder iterator to produce a list of values in the tree and verify that it is in sorted order to ensure that your rebalancing operations were performed correctly.
Explanation / Answer
//Self balancing binary search tree
public class BinaryTree<T> where T : IComparable<T>
{
private BinaryTreeNode<T> root;
public int Count;
public void Insert(T value)
{
BinaryTreeNode<T> node = new BinaryTreeNode<T>(value);
Insert(node);
}
public void Insert(BinaryTreeNode<T> node)
{
if (node == null)
{
throw new ArgumentNullException("node","node cannot be null");
}
if (root == null)
{
root = node;
}
else
{
Insert(node, ref root);
}
Count++;
}
public void Delete(T value, bool rebalanceTree)
{
BinaryTreeNode<T> parentNode;
BinaryTreeNode<T> foundNode = null;
BinaryTreeNode<T> tree = parentNode = root;
//Search for the node while keeping a reference to the parent
while (tree != null)
{
if (value.CompareTo(tree.Data) == 0)
{
foundNode = tree;
break;
}
else if (value.CompareTo(tree.Data) < 0)
{
parentNode = tree;
tree = tree.Left;
}
else if (value.CompareTo(tree.Data) > 0)
{
parentNode = tree;
tree = tree.Right;
}
}
if (foundNode == null)
{
throw new Exception("Node not found in binary tree");
}
bool leftOrRightNode = false;
if (foundNode != parentNode.Left)
{
leftOrRightNode = true;
}
if (foundNode == parentNode) //oh oh. We're trying to delete the root here.
{
if (rebalanceTree)
{
//Let's just remove the parent and rebalance the tree
//to ensure our tree will be nice and balanced
//after the removal
IList<BinaryTreeNode<T><binarytreenode<t>> listOfNodes =
new List<BinaryTreeNode<T><binarytreenode<t>>();
FillListInOrder(root, listOfNodes);
RemoveChildren(listOfNodes);
listOfNodes.Remove(parentNode);
root = null;
int count = Count - 1;
Count = 0;
BalanceTree(0, count - 1, listOfNodes);
}
else
{
//Regular way without balancing: just find the left-most node on the right
//side of the tree and that will become the root
BinaryTreeNode<T> leftMost = FindLeftMost(parentNode.Right, true);
if (leftMost != null)
{
leftMost.Left = parentNode.Left;
leftMost.Right = parentNode.Right;
root = leftMost;
}
}
}
else if (foundNode.Left == null && foundNode.Right == null) //This is a leaf node
{
//Just set it to null
if (leftOrRightNode)
{
parentNode.Right = null;
}
else
{
parentNode.Left = null;
}
}
else if (foundNode.Left != null &&
foundNode.Right != null) //This is a node with two children
{
if (leftOrRightNode)
{
parentNode.Right = foundNode.Right;
parentNode.Right.Left = foundNode.Left;
}
else
{
parentNode.Left = foundNode.Right;
parentNode.Left.Left = foundNode.Left;
}
}
else if (foundNode.Left != null ||
foundNode.Right != null) //This is a node with a single child
{
if (foundNode.Left != null)
{
if (leftOrRightNode)
{
parentNode.Right = foundNode.Left;
}
else
{
parentNode.Left = foundNode.Left;
}
}
else
{
if (leftOrRightNode)
{
parentNode.Right = foundNode.Right;
}
else
{
parentNode.Left = foundNode.Right;
}
}
}
}
public BinaryTreeNode<T> Search(T value)
{
BinaryTreeNode<T> tree = root;
while (root != null)
{
if (value.CompareTo(tree.Data) == 0)
{
return tree;
}
else if (value.CompareTo(tree.Data) < 0)
{
tree = tree.Left;
}
else if (value.CompareTo(tree.Data) > 0)
{
tree = tree.Right;
}
}
return null;
}
public IEnumerable<BinaryTreeNode<T>> InOrder()
{
return InOrder(root);
}
private IEnumerable<BinaryTreeNode<T>> InOrder(BinaryTreeNode<T> node)
{
if (node != null)
{
foreach(BinaryTreeNode<T> left in InOrder(node.Left))
{
yield return left;
}
yield return node;
foreach (BinaryTreeNode<T> right in InOrder(node.Right))
{
yield return right;
}
}
}
public IEnumerable<BinaryTreeNode<T>> PreOrder()
{
return PreOrder(root);
}
public IEnumerable<BinaryTreeNode<T>> PostOrder()
{
return PostOrder(root);
}
public IEnumerable<BinaryTreeNode<T>> BreadthFirstTraversal()
{
Queue<BinaryTreeNode<T>> queue = new Queue<BinaryTreeNode<T>>();
queue.Enqueue(root);
while (queue.Count != 0)
{
BinaryTreeNode<T> current = queue.Dequeue();
if (current != null)
{
queue.Enqueue(current.Left);
queue.Enqueue(current.Right);
yield return current;
}
}
}
public IEnumerable<BinaryTreeNode<T>> DepthFirstTraversal()
{
Stack<BinaryTreeNode<T>> queue = new Stack<BinaryTreeNode<T>>();
BinaryTreeNode<T> current;
queue.Push(root);
while (queue.Count != 0)
{
current = queue.Pop();
if (current != null)
{
queue.Push(current.Right);
queue.Push(current.Left);
yield return current;
}
}
}
public void BalanceTree()
{
IList<BinaryTreeNode<T>> listOfNodes = new List<BinaryTreeNode<T>>();
FillListInOrder(root, listOfNodes);
RemoveChildren(listOfNodes);
root = null;
int count = Count;
Count = 0;
BalanceTree(0, count - 1, listOfNodes);
}
private void Insert(BinaryTreeNode<T> node, ref BinaryTreeNode<T> parent)
{
if (parent == null)
{
parent = node;
}
else
{
if (node.Data.CompareTo(parent.Data) < 0)
{
Insert(node, ref parent.Left);
}
else if (node.Data.CompareTo(parent.Data) > 0)
{
Insert(node, ref parent.Right);
}
else if (node.Data.CompareTo(parent.Data) == 0)
{
throw new ArgumentException("Duplicate node");
}
}
}
private void BalanceTree(int min, int max,
IList<BinaryTreeNode<T>><binarytreenode<t> list)
{
if (min <= max)
{
int middleNode = (int)Math.Ceiling(((double)min + max) / 2);
Insert(list[middleNode]);
BalanceTree(min, middleNode - 1, list);
BalanceTree(middleNode + 1, max, list);
}
}
private void FillListInOrder(BinaryTreeNode<T> node,
ICollection<BinaryTreeNode<T>><binarytreenode<t> list)
{
if (node != null)
{
FillListInOrder(node.Left, list);
list.Add(node);
FillListInOrder(node.Right, list);
}
}
private void RemoveChildren(IEnumerable<BinaryTreeNode<T><binarytreenode<t>> list)
{
foreach(BinaryTreeNode<T> node in list)
{
node.Left = null;
node.Right = null;
}
}
private IEnumerable<BinaryTreeNode<T>> PreOrder(BinaryTreeNode<T> node)
{
if (node != null)
{
yield return node;
foreach (BinaryTreeNode<T><t> left in PreOrder(node.Left))
{
yield return left;
}
foreach (BinaryTreeNode<T> right in PreOrder(node.Right))
{
yield return right;
}
}
}
private IEnumerable<BinaryTreeNode<T>> PostOrder(BinaryTreeNode<T> node)
{
if (node != null)
{
foreach (BinaryTreeNode<T> left in PostOrder(node.Left))
{
yield return left;
}
foreach (BinaryTreeNode<T> right in PostOrder(node.Right))
{
yield return right;
}
yield return node;
}
}
private BinaryTreeNode<T> FindLeftMost(BinaryTreeNode<T> node, bool setParentToNull)
{
BinaryTreeNode<T> leftMost = null;
BinaryTreeNode<T> current = leftMost = node;
BinaryTreeNode<T> parent = null;
while (current != null)
{
if (current.Left!=null)
{
parent = current;
leftMost = current.Left;
}
current = current.Left;
}
if (parent!=null && setParentToNull)
{
parent.Left = null;
}
return leftMost;
}
}
public class BinaryTreeNode<T> where T : IComparable<T>
{
public BinaryTreeNode(T value)
{
Data = value;
}
public T Data
{
get;
set;
}
public BinaryTreeNode<T> Left;
public BinaryTreeNode<T> Right;
}