What tree balancing algorithms are you familiar with…

There are several main algorithms for tree balancing:

Rotation-based algorithms: These algorithms maintain balance by performing rotation operations during node insertion or deletion.

AVL trees: Maintain the condition that for each node, the difference in height between the left and right subtrees does not exceed 1.

struct Node {
    int key;
    Node *left, *right;
    int height;
};

// Function to get the height of a node
int height(Node *N) {
    if (N == NULL)
        return 0;
    return N->height;
}

// Function to compute the balance factor of a node
int getBalance(Node *N) {
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}

// Right rotation
Node *rightRotate(Node *y) {
    Node *x = y->left;
    Node *T2 = x->right;

    x->right = y;
    y->left = T2;

    y->height = 1 + max(height(y->left), height(y->right));
    x->height = 1 + max(height(x->left), height(x->right));

    return x;
}

Red-Black trees: Maintain balance by assigning colors (red or black) to nodes and following a set of rules.

enum Color { RED, BLACK };

struct Node {
    int key;
    Node *left, *right, *parent;
    Color color;
};

// Function to insert a node and balance
Node* insert(Node* root, Node* pt) {
    // Standard BST insertion
    if (root == NULL) return pt;

    if (pt->key < root->key) {
        root->left = insert(root->left, pt);
        root->left->parent = root;
    } else if (pt->key > root->key) {
        root->right = insert(root->right, pt);
        root->right->parent = root;
    }

    return root; // TODO: Implement balancing
}

Treaps: Combine properties of binary search trees and heaps. Each node has a key and a priority. They are structured so that they are a search tree by keys and a heap by priorities.

B-trees and their variants (B-trees, B+-trees, B-trees):* Often used for external storage data (disks) to minimize I/O operations. Each node can have multiple children.

Algorithm	Properties	Application
AVL trees	Strictly balanced by height. Fast search operations.	In-memory search.
Red-Black trees	Not strictly height-balanced, but guarantees logarithmic height. Fast insert/delete operations.	Sets (std::set), maps (std::map) in C++.
Treaps	Probabilistically balanced. Simple insert/delete operations.	Data structures requiring random balancing.
B-trees	Optimized for disk operations.	File systems, databases.

What tree balancing algorithms are you familiar with?