Describe the concept of a self-balancing binary search tree, and explain how an AVL tree and a Red-Black tree work.? — Data Structures & Algorithms Interview Question #43

A self-balancing binary search tree is a binary search tree that automatically adjusts its structure to maintain a balanced tree, ensuring efficient search, insertion, and deletion operations. The goal of a self-balancing binary search tree is to maintain a balance between the left and right subtrees of each node, preventing one subtree from being significantly deeper than the other.

AVL trees and Red-Black trees are two commonly used types of self-balancing binary search trees.

AVL Tree: An AVL tree is a self-balancing binary search tree in which the height of the left and right subtrees of each node differs by at most one. To maintain this property, the AVL tree uses a balancing operation called a rotation. A rotation is a local transformation that preserves the order of the tree but changes the structure of the tree by rearranging nodes.

When a node is inserted into an AVL tree, the tree is checked for balance. If the height of the left and right subtrees of a node differs by more than one, a rotation is performed to balance the tree. AVL trees can perform both left and right rotations, which can be single or double rotations depending on the structure of the tree.

Here is an example of an AVL tree insertion operation:

// insert 4 into the following AVL tree
//     6
//    / \
//   3   9
//  / \
// 1   5

// After insertion:
//      6
//     / \
//    4   9
//   / \
//  3   5
// /
//1

AVLNode insert(AVLNode root, int value) {
    if (root == null) {
        return new AVLNode(value);
    }

    if (value < root.value) {
        root.left = insert(root.left, value);
    } else {
        root.right = insert(root.right, value);
    }

    int balance = getBalance(root);

    if (balance > 1 && value < root.left.value) {
        return rightRotate(root);
    }

    if (balance < -1 && value > root.right.value) {
        return leftRotate(root);
    }

    if (balance > 1 && value > root.left.value) {
        root.left = leftRotate(root.left);
        return rightRotate(root);
    }

    if (balance < -1 && value < root.right.value) {
        root.right = rightRotate(root.right);
        return leftRotate(root);
    }

    return root;
}

int getHeight(AVLNode node) {
    if (node == null) {
        return 0;
    }

    return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}

int getBalance(AVLNode node) {
    if (node == null) {
        return 0;
    }

    return getHeight(node.left) - getHeight(node.right);
}

AVLNode rightRotate(AVLNode y) {
    AVLNode x = y.left;
    AVLNode T2 = x.right;

    x.right = y;
    y.left = T2;

    return x;
}

AVLNode leftRotate(AVLNode x) {
    AVLNode y = x.right;
    AVLNode T2 = y.left;

    y.left = x;
    x.right = T2;

    return y;
}

Red-Black Tree: A Red-Black tree is another type of self-balancing binary search tree. It maintains a balance between the left and right subtrees of each node by coloring each node either red or black. The color of the node determines the balance of the tree, and the structure of the tree is adjusted to maintain a balance when new nodes are added or removed.