CSCE3110.070 Balanced BST

Implement Balanced Binary Search Tree in C++.

You can implement it as AVL or Red-Black tree. Your tree class BalancedBinarySearchTree should support the following Interfaces:

bool InsertNode(int key) - inserts a node into the tree.
bool DeleteNode(int key) - delete a node with that key;
Node* FindNode(int key) - returns a pointer to the node in the tree.
void PrintLevelKeys() - prints tree node keys using In-Level Traversal (see below).
int GetNodeBalanceProperty() - returns the height or color of a tree.
int Count() - returns number of nodes.

Notes:

Your program should have Node structure/class defined as public.

Implement In-Level traversal algorithm below that will print node keys level by level (remember, meaning of height here is different from height of AVL node) Example: the following tree see image.

should be printed:

20
12 23
11 * 21 30

PrintLevels(root)
  Height = GetHeight(root)
  For i=1 to Height
    PrintLevel(root, i)

PrintLevel(node, level)
  If(level == 1)
    Print(node.key)
  Else
    PrintLevel(node->left, level-1)
    PrintLevel(node->right, level-1)