Binary Search Trees

Binary search trees are a special type of binary trees that satisfies the following at any node:

All nodes in left subtree are smaller than root node
All nodes in the right subtree are greater than root node

Functions

Insertion
Removing an item
Searching
Finding minimum
Finding maximum

Search

Insertion

We search for the right place to insert the new node by having a private method that gets called recursively
Note that here it is assumed that no duplicate values are allowed in the BST

insertInOrder

template<typename T>
BinaryNode<T>* BinarySearchTree<T>::insertInorder(BinaryNode<T>* subTreePtr, T target)
{
    if (subTreePtr == nullptr)
        subTreePtr = new BinaryNode<T>(target);
    else if ( target < subTreePtr->getItem())
        subTreePtr->setLeft(insertInorder(subTreePtr->getLeftChild(), target));
    else
        subTreePtr->setRight(insertInorder(subTreePtr->getRightChild(), target));

    return subTreePtr;
}

add()

The public method that allocates calls InsertInOrder()

template <typename T>
bool BinarySearchTree<T>::add(const T& newItem)
{
	rootPtr = insertInOrder(rootPtr, newItem);
	return true;
}

Note

taking the output of a preoder traversal of a binray search tree and using it with inserInOrder will create a binary tree similar to the orignal one -> in fact this is used in the copy constructor of the tree

Remove

Removing an element is more tricky than inserting we have three possible scenarios for the node to delete it can be:

A leaf node
A parent node with one child
A parent node with 2 children nodes

First case is quiet easy just remove the node itself by setting it to null and nothing extra needs to be done

Second case: can further be divided into another two cases -> has only left child or has only the right child (both has the same solution due to symmetry)

Suppose you delete that node that will leave the child node without a parent so to avoid that we first swap parent node we want to delete with the child node -> the node we want to delete is now a leaf node and we are back to the first case

Third case: when the node is a parent node with 2 children

we won't be deleting the node itself directly, just like we did with case 2 we will find another node that is easier to delete and swap their items, lets call the node we want to delete N and the Node that will take its place M

Steps:

Locate another node M that is easier to remove from the tree than the node N
Copy the item that is in M to N , thus effectively removing from the tree the item originally in N
Remove the node M from the tree

Now the problem has changed to how can we find node M that satisfy the following:

must be greater than all elements in left sub-tree
must be smaller than all elements in the right sub-tree

There are two nodes that satisifay both conditions:

Maximum node in the left subtree "inorder predecessor" -> rightmost child of the left subtree
Minimum node in the right subtree "inorder successor" -> leftmost child of the rightsubtree

For example for 20:

Inorder predecessor is 19
Inorder successor is 30

To find inorder predecessor:

BinaryNode<T>* current = rootPtr->getLeftChild();

while (current && current->getRightChild())
    current = current->getRightChild();

To find inorder successor:

BinaryNode<T>* current = rootPtr->getRightChild();

while (current && current->getLeftChild())
    current = current->getLeftChild();

Recursive remove function (private)

template<typename T>
inline BinaryNode<T>* BinarySearchTree<T>::removeValue(BinaryNode<T>* rootPtr, const T& target, bool& success)
{
    if (rootPtr == nullptr)
        return nullptr;
    else if (target < rootPtr->getItem()) 
        rootPtr->setLeft(removeValue(rootPtr->getLeftChild(), target, success));
    else if (target > rootPtr->getItem())
        rootPtr->setRight(removeValue(rootPtr->getRightChild(), target, success));

    else // target is found 
    {
        if (rootPtr->getLeftChild() == nullptr)
        {
            BinaryNode<T>* temp = rootPtr->getRightChild();
            delete rootPtr;
            return temp;
        }

        else if (rootPtr->getRightChild() == nullptr)
        {
            BinaryNode<T>* temp = rootPtr->getLeftChild();
            delete rootPtr;
            return temp;
        }

        else // find min in the right subtree (in left subtree of it)
        {
            success = true;

            BinaryNode<T>* current = rootPtr->getRightChild();
            T newItem = current->getItem();

            while (current->getLeftChild())
                current = current->getLeftChild();
            rootPtr->setItem(newItem);
            rootPtr->setRight(removeValue(rootPtr->getRightChild(), newItem, success));
        }
    }
    return rootPtr;
}

Now the public method that calls it, returns true if element was found and deleted

template<typename T>
bool BinarySearchTree<T>::remove(const T& anEntry)
{
    bool success = false;
    removeValue(rootPtr, anEntry, success);
    return success;
}

Searching

Searching for an element in a Binary Search Tree (BST) is a very efficient operation due to the inherent ordering property of the tree. Here's a breakdown of how it works:

Start at the Root:
Compare with Current Node:
Three Possibilities:
- Target Found
- Target Less Than Current: If the target value is less than the current node's data, the search continues by moving to the left child of the current node.
- Target Greater Than Current: If the target value is greater than the current node's data, the search continues by moving to the right child of the current node.
Repeat Until Found or Reach Null The private method is recursively implemented as follows:

template<typename T>
inline BinaryNode<T*> BinarySearchTree<T>::search(BinaryNode<T>* subtreePtr, const T& target)
{
	if (!subtreePtr)
		return nullptr;

	if (subtreePtr->getItem() == target)
		return subtreePtr;
	if (subtreePtr->getItem() < target)
		return search(subtreePtr->getRightChildPtr(), target);
	else
		return search(subtreePtr->getLeftChildPtr(), target);
}

The public method then calls it and return true if it didn't return a nullptr as follows:

template<typename T>
inline bool BinarySearchTree<T>::isFound(const T& target)
{
	return search(rootPtr, target);
}

Finding minimum

The smallest element in a BST can be easily found by reaching the leaf of the root's left child

template<typename T>
T BinarySearchTree<T>::findMinimumHelper(BinaryNode<T>* subtreePtr)
{
	if (!subtreePtr->getLeftChildPtr())
		return subtreePtr->getItem();
	T temp = findMinimum(subtreePtr->getLeftChildPtr());
}

Finding maximum

Similarly The largest element in a BST is the leaf of the root's right child

template<typename T>
T BinarySearchTree<T>::findMaximumHelper(BinaryNode<T>* subtreePtr)
{
	if (!subtreePtr->getRightChildPtr())
		return subtreePtr->getItem();
	T temp = findMaximum(subtreePtr->getRightChildPtr());
}

Both helper functions get called inside their public versions T findMinimum() & T findMaximim() easily.

AVL Trees

While BSTs excel at searching and insertion due to their sorted structure, their performance can be heavily influenced by the order of element insertion. Adding elements in increasing or decreasing order creates a skewed or degenerate BST, turning it into a linked list making the complexity of the code O(n) instead of logarithmic. That is where self balancing trees come in, there are many types of self balancing BST

AVL trees
Red-Black trees

The basic strategy of the AVL algorithm is to monitor the shape of the binary search tree after each insertion or deletion if the tree becomes imbalanced we "rotate" it where at any node The heights of the left and right subtrees differ by no more than one

Balance of AVL tree = Height of left subtree - Height of right subtree, -1 <= balance factor <= 1

We need to keep track of each node's height, we will add it as a data member in node class

template <typename T>
class BinaryNode
{
private:
    T item;
    BinaryNode<T>* leftChild;
    BinaryNode<T>* rightChild;
    int height;
}

We will also need to define a private method to get the balance factor of each node

template<typename T>
int AVLTree<T>::getBalanceFactor(BinaryNode<T>* nodePtr) const
{
    int leftHeight = getHeightHelper(nodePtr->getLeftChild());
    int rightHeight = getHeightHelper(nodePtr->getRightChild());
    
    return std::max(leftHeight, rightHeight);
}

All cases that we need to re-balance

If the tree becomes left heavy

If the tree becomes right heavy

For left of left and right of right cases they require only one rotation to be fixed:

Right Rotation function:

template<typename T>
BinaryNode<T>* AVLTree<T>::rightRotate(BinaryNode<T>* currentRoot)
{
    BinaryNode<T>* newRoot = currentRoot->getLeftChild();

    currentRoot->setLeftChild(newRoot->getRightChild());
    newRoot->setRightChild(currentRoot);

    // Update heights
    currentRoot->setHeight(getHeightHelper(root));
    newRoot->setHeight(getHeightHelper(newRoot));
    
    if (currentRoot == rootPtr)
        rootPtr = newRoot;
        
    return newRoot;
}

Left Rotation function:

template<typename T>
inline BinaryNode<T>* AVLTree<T>::leftRotate(BinaryNode<T>* currentRoot)
{
    BinaryNode<T>* newRoot = currentRoot->getRightChild();

    currentRoot->setRightChild(newRoot->getLeftChild());
    newRoot->setLeftChild(root);

    // Update heights
    currentRoot->setHeight(getHeightHelper(root));
    newRoot->setHeight(getHeightHelper(newRoot));

    if (currentRoot = rootPtr)
        rootPtr = newRoot;

    return newRoot;
}

For the other two cases we will perform double rotations:

insert

It is quite similar to BST insertion we just check the balance after and re-balance the tree if needed

template<class T>
inline BinaryNode<T>* AVLTree<T>::insert(BinaryNode<T>* subTreePtr, T target)
{
    // First perform normal BST insertion
    if (subTreePtr == nullptr)
        subTreePtr = new BinaryNode<T>(target);
    else if (target < subTreePtr->getItem())
        subTreePtr->setLeftChild(insert(subTreePtr->getLeftChild(), target));
    else
        subTreePtr->setRightChild(insert(subTreePtr->getRightChild(), target));

    return subTreePtr;

    // Update the height 
    subTreePtr->setHeight(getHeightHelper(subTreePtr));

    // Check the balance factor after insertion
    int balance = getBalanceFactor(subTreePtr);

    if (balance > 1) // Left heavy
    {
	int childBalance = getBalanceFactor(subTreePtr->getLeftChild());
        if (childBalance < 0)
            subTreePtr->setLeftChild(leftRotate(subTreePtr)); // right of left

        return rightRotate(subTreePtr); // left of left 
    }

    if (balance < -1) // right heavy
    {
	int childBalance = getBalanceFactor(subTreePtr->getRightChild());
        if (childBalance > 0)
            subTreePtr->setRightChild(rightRotate(subTreePtr)); // left of right

        return leftRotate(subTreePtr); // right of right 
    }

    return subTreePtr;
}

remove

template<typename T>
inline BinaryNode<T>* AVLTree<T>::removeValue(BinaryNode<T>* subTreePtr, const T& target, bool& success)
{
    if (subTreePtr == nullptr)
        return nullptr;
    else if (target < subTreePtr->getItem())
        subTreePtr->setLeftChild(removeValue(subTreePtr->getLeftChild(), target, success));
    else if (target > rootPtr->getItem())
        subTreePtr->setRightChild(removeValue(subTreePtr->getRightChild(), target, success));

    else // target is found 
    {
        if (subTreePtr->getLeftChild() == nullptr)
        {
            BinaryNode<T>* temp = subTreePtr->getRightChild();
            delete subTreePtr;
            return temp;
        }

        else if (subTreePtr->getRightChild() == nullptr)
        {
            BinaryNode<T>* temp = subTreePtr->getLeftChild();
            delete subTreePtr;
            return temp;
        }

        else // find min in the right subtree (in left subtree of it)
        {
            success = true;

            BinaryNode<T>* current = subTreePtr->getRightChild();
            T newItem = current->getItem();

            while (current->getLeftChild())
                current = current->getLeftChild();
            subTreePtr->setItem(newItem);
            subTreePtr->setRightChild(removeValue(rootPtr->getRightChild(), newItem, success));
        }
    }
    return subTreePtr;

    // Update the height 
    subTreePtr->setHeight(getHeightHelper(subTreePtr));

    // Check the balance factor after insertion
    int balance = getBalanceFactor(subTreePtr);

    if (balance > 1) // Left heavy
    {
	int childBalance = getBalanceFactor(subTreePtr->getLeftChild());

        if (childBalance < 0)
            subTreePtr->setLeftChild(leftRotate(subTreePtr)); // right of left 
        return rightRotate(subTreePtr); // left of left 
    }

    if (balance < -1) // right heavy
    {
	int childBalance = getBalanceFactor(subTreePtr->getRightChild());

        if ( childBalance > 0)
            subTreePtr->setRightChild(rightRotate(subTreePtr)); // left of right
        return leftRotate(subTreePtr); // right of right 
    }

    return subTreePtr;
}

Useful Videos

BST

AVL

Useful Articles

Everything about binary search trees | medium

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Contents

Binary Search Trees

Functions

Search

Insertion

insertInOrder

add()

Remove

Searching

Finding minimum

Finding maximum

AVL Trees

AVL tree Functions

All cases that we need to re-balance

If the tree becomes left heavy

If the tree becomes right heavy

For left of left and right of right cases they require only one rotation to be fixed:

For the other two cases we will perform double rotations:

insert

remove

Useful Videos

Useful Articles

For practice

FilesExpand file tree

ValueOrientedTrees.md

Latest commit

History

ValueOrientedTrees.md

File metadata and controls

Contents

Binary Search Trees

Functions

Search

Insertion

insertInOrder

add()

Remove

Searching

Finding minimum

Finding maximum

AVL Trees

AVL tree Functions

All cases that we need to re-balance

If the tree becomes left heavy

If the tree becomes right heavy

For left of left and right of right cases they require only one rotation to be fixed:

For the other two cases we will perform double rotations:

insert

remove

Useful Videos

Useful Articles

For practice