W3Schools Tryit Editor

Python

Java

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 1

def getHeight(node):
    if not node:
        return 0
    return node.height

def getBalance(node):
    if not node:
        return 0
    return getHeight(node.left) - getHeight(node.right)

def rightRotate(y):
    x = y.left
    T2 = x.right
    x.right = y
    y.left = T2
    y.height = 1 + max(getHeight(y.left), getHeight(y.right))
    x.height = 1 + max(getHeight(x.left), getHeight(x.right))
    return x

def leftRotate(x):
    y = x.right
    T2 = y.left
    y.left = x
    x.right = T2
    x.height = 1 + max(getHeight(x.left), getHeight(x.right))
    y.height = 1 + max(getHeight(y.left), getHeight(y.right))
    return y

def insert(node, data):
    if not node:
        return TreeNode(data)

if data < node.data:
        node.left = insert(node.left, data)
    elif data > node.data:
        node.right = insert(node.right, data)

node.height = 1 + max(getHeight(node.left), getHeight(node.right))
    balance = getBalance(node)

# Left Left
    if balance > 1 and data < node.left.data:
        return rightRotate(node)

# Right Right
    if balance < -1 and data > node.right.data:
        return leftRotate(node)

# Left Right
    if balance > 1 and data > node.left.data:
        node.left = leftRotate(node.left)
        return rightRotate(node)

# Right Left
    if balance < -1 and data < node.right.data:
        node.right = rightRotate(node.right)
        return leftRotate(node)

return node

def inOrderTraversal(node):
    if node is None:
        return
    inOrderTraversal(node.left)
    print(node.data, end=", ")
    inOrderTraversal(node.right)
    
def minValueNode(node):
    current = node
    while current.left is not None:
        current = current.left
    return current

def minValueNode(node):
    current = node
    while current.left is not None:
        current = current.left
    return current

def delete(node, data):
    if not node:
        return node

if data < node.data:
        node.left = delete(node.left, data)
    elif data > node.data:
        node.right = delete(node.right, data)
    else:
        if node.left is None:
            temp = node.right
            node = None
            return temp
        elif node.right is None:
            temp = node.left
            node = None
            return temp

temp = minValueNode(node.right)
        node.data = temp.data
        node.right = delete(node.right, temp.data)

if node is None:
        return node

# Update the balance factor and balance the tree
    node.height = 1 + max(getHeight(node.left), getHeight(node.right))
    balance = getBalance(node)

# Balancing the tree
    # Left Left
    if balance > 1 and getBalance(node.left) >= 0:
        return rightRotate(node)

# Left Right
    if balance > 1 and getBalance(node.left) < 0:
        node.left = leftRotate(node.left)
        return rightRotate(node)

# Right Right
    if balance < -1 and getBalance(node.right) <= 0:
        return leftRotate(node)

# Right Left
    if balance < -1 and getBalance(node.right) > 0:
        node.right = rightRotate(node.right)
        return leftRotate(node)

return node

# Inserting the letters
root = None
letters = ['C', 'B', 'E', 'A', 'D', 'H', 'G', 'F']
for letter in letters:
    root = insert(root, letter)

inOrderTraversal(root)
print('\nDeleting A')
root = delete(root,'A')
inOrderTraversal(root)

#Python

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
    int height;
} TreeNode;

int max(int a, int b) {
    return (a > b) ? a : b;
}

int getHeight(TreeNode *N) {
    if (N == NULL)
        return 0;
    return N->height;
}

TreeNode* newNode(int data) {
    TreeNode* node = (TreeNode*) malloc(sizeof(TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;  // new node is initially added at leaf
    return(node);
}

TreeNode *rightRotate(TreeNode *y) {
    TreeNode *x = y->left;
    TreeNode *T2 = x->right;
    x->right = y;
    y->left = T2;
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    return x;
}

TreeNode *leftRotate(TreeNode *x) {
    TreeNode *y = x->right;
    TreeNode *T2 = y->left;
    y->left = x;
    x->right = T2;
    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
    return y;
}

int getBalance(TreeNode *N) {
    if (N == NULL)
        return 0;
    return getHeight(N->left) - getHeight(N->right);
}

TreeNode* insert(TreeNode* node, int data) {
    if (node == NULL)
        return(newNode(data));

if (data < node->data)
        node->left = insert(node->left, data);
    else if (data > node->data)
        node->right = insert(node->right, data);
    else // Equal data not allowed in BST
        return node;

node->height = 1 + max(getHeight(node->left), getHeight(node->right));

int balance = getBalance(node);

// Left Left Case
    if (balance > 1 && data < node->left->data)
        return rightRotate(node);

// Right Right Case
    if (balance < -1 && data > node->right->data)
        return leftRotate(node);

// Left Right Case
    if (balance > 1 && data > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

// Right Left Case
    if (balance < -1 && data < node->right->data) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

return node;
}

TreeNode * minValueNode(TreeNode* node) {
    TreeNode* current = node;
    while (current->left != NULL)
        current = current->left;
    return current;
}

void inOrderTraversal(TreeNode *root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%c ", root->data);
        inOrderTraversal(root->right);
    }
}

TreeNode* deleteNode(TreeNode* root, int data) {
    if (root == NULL)
        return root;

// Standard BST delete
    if (data < root->data)
        root->left = deleteNode(root->left, data);
    else if (data > root->data)
        root->right = deleteNode(root->right, data);
    else {
        if ((root->left == NULL) || (root->right == NULL)) {
            TreeNode *temp = root->left ? root->left : root->right;
            if (temp == NULL) {
                temp = root;
                root = NULL;
            } else
                *root = *temp;
            free(temp);
        } else {
            TreeNode* temp = minValueNode(root->right);
            root->data = temp->data;
            root->right = deleteNode(root->right, temp->data);
        }
    }

if (root == NULL)
        return root;

root->height = 1 + max(getHeight(root->left), getHeight(root->right));

int balance = getBalance(root);

// Left Left Case
    if (balance > 1 && getBalance(root->left) >= 0)
        return rightRotate(root);

// Left Right Case
    if (balance > 1 && getBalance(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

// Right Right Case
    if (balance < -1 && getBalance(root->right) <= 0)
        return leftRotate(root);

// Right Left Case
    if (balance < -1 && getBalance(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

return root;
}

int main() {
    TreeNode *root = NULL;
    char letters[] = {'C', 'B', 'E', 'A', 'D', 'H', 'G', 'F'};
    int n = sizeof(letters) / sizeof(letters[0]);
    for (int i = 0; i < n; i++) {
        root = insert(root, letters[i]);
    }

inOrderTraversal(root);

printf("\nDeleting 'A'\n");
    root = deleteNode(root, 'A');

inOrderTraversal(root);
    return 0;
}

//C

public class Main {
    static class AVLTree {
        class TreeNode {
            char data;
            TreeNode left, right;
            int height;

TreeNode(char d) {
                data = d;
                height = 1;
            }
        }

TreeNode root;

private int height(TreeNode N) {
            if (N == null) return 0;
            return N.height;
        }

private int getBalance(TreeNode N) {
            if (N == null) return 0;
            return height(N.left) - height(N.right);
        }

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

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

y.height = Math.max(height(y.left), height(y.right)) + 1;
            x.height = Math.max(height(x.left), height(x.right)) + 1;

return x;
        }

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

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

x.height = Math.max(height(x.left), height(x.right)) + 1;
            y.height = Math.max(height(y.left), height(y.right)) + 1;

return y;
        }

TreeNode insert(TreeNode node, char data) {
            if (node == null) return new TreeNode(data);

if (data < node.data) node.left = insert(node.left, data);
            else if (data > node.data) node.right = insert(node.right, data);
            else return node;

node.height = 1 + Math.max(height(node.left), height(node.right));

int balance = getBalance(node);

// Left Left Case
            if (balance > 1 && data < node.left.data)
                return rightRotate(node);

// Right Right Case
            if (balance < -1 && data > node.right.data)
                return leftRotate(node);

// Left Right Case
            if (balance > 1 && data > node.left.data) {
                node.left = leftRotate(node.left);
                return rightRotate(node);
            }

// Right Left Case
            if (balance < -1 && data < node.right.data) {
                node.right = rightRotate(node.right);
                return leftRotate(node);
            }

return node;
        }

private TreeNode minValueNode(TreeNode node) {
            TreeNode current = node;
            while (current.left != null) {
                current = current.left;
            }
            return current;
        }

TreeNode delete(TreeNode root, char data) {
            if (root == null)
                return root;

if (data < root.data)
                root.left = delete(root.left, data);
            else if (data > root.data)
                root.right = delete(root.right, data);
            else {
                if ((root.left == null) || (root.right == null)) {
                    TreeNode temp = null;
                    if (temp == root.left)
                        temp = root.right;
                    else
                        temp = root.left;

if (temp == null) {
                        temp = root;
                        root = null;
                    } else
                        root = temp;
                } else {
                    TreeNode temp = minValueNode(root.right);
                    root.data = temp.data;
                    root.right = delete(root.right, temp.data);
                }
            }

if (root == null)
                return root;

root.height = Math.max(height(root.left), height(root.right)) + 1;

int balance = getBalance(root);

// Left Left Case
            if (balance > 1 && getBalance(root.left) >= 0)
                return rightRotate(root);

// Left Right Case
            if (balance > 1 && getBalance(root.left) < 0) {
                root.left = leftRotate(root.left);
                return rightRotate(root);
            }

// Right Right Case
            if (balance < -1 && getBalance(root.right) <= 0)
                return leftRotate(root);

// Right Left Case
            if (balance < -1 && getBalance(root.right) > 0) {
                root.right = rightRotate(root.right);
                return leftRotate(root);
            }

return root;
        }

void inOrderTraversal(TreeNode node) {
            if (node != null) {
                inOrderTraversal(node.left);
                System.out.print(node.data + ", ");
                inOrderTraversal(node.right);
            }
        }

public static void main(String[] args) {
            AVLTree tree = new AVLTree();
            char[] letters = {'C', 'B', 'E', 'A', 'D', 'H', 'G', 'F'};
            for (char letter : letters) {
                tree.root = tree.insert(tree.root, letter);
            }

tree.inOrderTraversal(tree.root);

System.out.println("\nDeleting A");
            tree.root = tree.delete(tree.root, 'A');
            tree.inOrderTraversal(tree.root);
        }
    }
}

// Java