AVL Tree Data Structures

Data Structures: AVL Tree Data Structure

The Definition of a AVL Tree

An AVL tree is a self-balancing binary search tree where the difference between heights of left and right subtrees cannot be more than one for all nodes.

Creating an AVL tree involves

Establishing a structure for the tree node.
Defining the AVL tree itself.
Implementing rotations to keep the tree balanced.

Let's break down the steps:

1. Define the Node

A node in the AVL tree contains a key, pointers to its left and right children, and a height value to store the height of the node.

class AVLNode {
    constructor(key) {
        this.key = key;
        this.left = null;
        this.right = null;
        this.height = 1;  // Height is initially set to 1 for a new node
    }
}

2. Define the AVL Tree

This tree will have functions for insertion, deletion, searching, and utilities for balancing.

class AVLTree {
    constructor() {
        this.root = null;
    }
    
    // Utility function to get height of a node
    getHeight(node) {
        return node ? node.height : 0;
    }
    
    // Utility function to update height of a node
    updateHeight(node) {
        node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
    }
    
    // Utility function to get balance factor of a node
    getBalance(node) {
        return this.getHeight(node.left) - this.getHeight(node.right);
    }
}

3. Implement Rotations

For the AVL tree to remain balanced, we need four types of rotations:

Right Rotation (RR)
Left Rotation (LL)
Left Right Rotation (LR)
Right Left Rotation (RL)

// ... Inside AVLTree class

// Right rotation
rightRotate(y) {
    const x = y.left;
    const T3 = x.right;

    x.right = y;
    y.left = T3;

    this.updateHeight(y);
    this.updateHeight(x);

    return x;  // new root
}

// Left rotation
leftRotate(x) {
    const y = x.right;
    const T2 = y.left;

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

    this.updateHeight(x);
    this.updateHeight(y);

    return y;  // new root
}

4. Implement Insertion

Insertion in an AVL tree follows similar logic to a regular binary search tree (BST), but after every insertion, we need to check for balance and perform necessary rotations.

// ... Inside AVLTree class

insert(root, key) {
    if (!root) {
        return new AVLNode(key);
    }

    if (key < root.key) {
        root.left = this.insert(root.left, key);
    } else if (key > root.key) {
        root.right = this.insert(root.right, key);
    } else {
        return root;  // Duplicate keys are not allowed
    }

    this.updateHeight(root);
    
    const balance = this.getBalance(root);

    // Perform rotations if the node becomes unbalanced
    if (balance > 1) {
        if (key < root.left.key) {
            return this.rightRotate(root);
        } else {
            root.left = this.leftRotate(root.left);
            return this.rightRotate(root);
        }
    }

    if (balance < -1) {
        if (key > root.right.key) {
            return this.leftRotate(root);
        } else {
            root.right = this.rightRotate(root.right);
            return this.leftRotate(root);
        }
    }

    return root;
}

// Wrapper method for insertion
add(key) {
    this.root = this.insert(this.root, key);
}

5. Implement Deletion (Optional but Important)

Deleting a node from an AVL tree involves deleting as in a BST followed by rotations to ensure the tree remains balanced.

6. Additional Utilities

You might want to implement utilities for searching, in-order traversal, pre-order traversal, etc.

note

The provided structure gives you a basic overview of AVL tree creation in JavaScript. Note that certain complexities arise during node deletion and handling different cases for rotations. Depending on your application and needs, you may need to expand on this foundation.

Complexity

AVL Trees are a type of self-balancing binary search tree, and the balancing ensures that the tree remains approximately balanced, resulting in logarithmic time complexities for most operations. Here's a table for the time and space complexities of common operations in an AVL Tree:

Operation	Average Time Complexity	Worst Case Time Complexity	Space Complexity
Insertion	O(log n)	O(log n)	O(log n)
Deletion	O(log n)	O(log n)	O(log n)
Search	O(log n)	O(log n)	O(log n)
Minimum/Maximum	O(log n)	O(log n)	O(log n)
Predecessor/Successor	O(log n)	O(log n)	O(log n)
Rotation (balancing)	O(1)	O(1)	O(1)

Notes:

Insertion, Deletion, and Search: The AVL tree maintains its balance through rotations after insertions and deletions, ensuring that the height of the tree remains at most logarithmic in relation to the number of nodes. This gives the logarithmic complexities for these operations.
Minimum/Maximum: The minimum (or maximum) is the leftmost (or rightmost) node, which can be found by following left (or right) child pointers from the root, taking O(log n) time in the worst case.
Predecessor/Successor: Given a node, finding its predecessor or successor involves either going up the tree or down to the left or right subtree. Again, due to the height constraint, it takes O(log n) in the worst case.
Rotation (balancing): AVL Trees use simple rotations (single or double) to re-balance the tree after an insertion or deletion. These rotations are constant time operations as they involve just a few pointer updates.

For Space Complexity, each operation requires a stack space proportional to the height of the tree, which is O(log n) in the worst case due to the balancing nature of AVL Trees.

The Definition of a AVL Tree​

Creating an AVL tree involves​

1. Define the Node​

2. Define the AVL Tree​

3. Implement Rotations​

4. Implement Insertion​

5. Implement Deletion (Optional but Important)​

6. Additional Utilities​

Complexity​