AVL Tree

pick a language to open the code

class Node:
    def __init__(self, key):
        self.key = key
        self.height = 0
        self.left = self.right = None


def height(node):
    return -1 if node is None else node.height


def fix(node):
    node.height = 1 + max(height(node.left), height(node.right))


def rotate(node, to_right):
    pivot = node.left if to_right else node.right
    if to_right:
        node.left, pivot.right = pivot.right, node
    else:
        node.right, pivot.left = pivot.left, node
    fix(node)
    fix(pivot)
    return pivot


def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)
    fix(node)
    slant = height(node.left) - height(node.right)
    if slant > 1:
        if height(node.left.left) < height(node.left.right):
            node.left = rotate(node.left, False)
        return rotate(node, True)
    if slant < -1:
        if height(node.right.right) < height(node.right.left):
            node.right = rotate(node.right, True)
        return rotate(node, False)
    return node

function makeNode(key) {
  return { key, height: 0, left: null, right: null };
}

function height(node) {
  return node === null ? -1 : node.height;
}

function fix(node) {
  node.height = 1 + Math.max(height(node.left), height(node.right));
}

function rotate(node, toRight) {
  const pivot = toRight ? node.left : node.right;
  if (toRight) {
    node.left = pivot.right;
    pivot.right = node;
  } else {
    node.right = pivot.left;
    pivot.left = node;
  }
  fix(node);
  fix(pivot);
  return pivot;
}

function insert(node, key) {
  if (node === null) return makeNode(key);
  if (key < node.key) node.left = insert(node.left, key);
  else node.right = insert(node.right, key);
  fix(node);
  const slant = height(node.left) - height(node.right);
  if (slant > 1) {
    const kid = node.left;
    if (height(kid.left) < height(kid.right)) node.left = rotate(kid, false);
    return rotate(node, true);
  }
  if (slant < -1) {
    const kid = node.right;
    if (height(kid.right) < height(kid.left)) node.right = rotate(kid, true);
    return rotate(node, false);
  }
  return node;
}

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

static int height(Node* n) { return n == NULL ? -1 : n->height; }

static void fix(Node* n) {
    int a = height(n->left), b = height(n->right);
    n->height = 1 + (a > b ? a : b);
}

static Node* rotate(Node* n, int to_right) {
    Node* pivot = to_right ? n->left : n->right;
    if (to_right) { n->left = pivot->right; pivot->right = n; }
    else { n->right = pivot->left; pivot->left = n; }
    fix(n);
    fix(pivot);
    return pivot;
}

Node* insert(Node* n, int key) {
    if (n == NULL) {
        Node* fresh = calloc(1, sizeof(Node));
        fresh->key = key;
        return fresh;
    }
    if (key < n->key) n->left = insert(n->left, key);
    else n->right = insert(n->right, key);
    fix(n);
    int slant = height(n->left) - height(n->right);
    if (slant > 1) {
        if (height(n->left->left) < height(n->left->right))
            n->left = rotate(n->left, 0);
        return rotate(n, 1);
    }
    if (slant < -1) {
        if (height(n->right->right) < height(n->right->left))
            n->right = rotate(n->right, 1);
        return rotate(n, 0);
    }
    return n;
}

struct Node {
    int key;
    int height = 0;
    Node* left = nullptr;
    Node* right = nullptr;
};

int height_of(Node* n) { return n == nullptr ? -1 : n->height; }

void fix(Node* n) {
    n->height = 1 + std::max(height_of(n->left), height_of(n->right));
}

Node* rotate(Node* n, bool to_right) {
    Node* pivot = to_right ? n->left : n->right;
    if (to_right) { n->left = pivot->right; pivot->right = n; }
    else { n->right = pivot->left; pivot->left = n; }
    fix(n);
    fix(pivot);
    return pivot;
}

Node* insert(Node* n, int key) {
    if (n == nullptr) return new Node{key};
    if (key < n->key) n->left = insert(n->left, key);
    else n->right = insert(n->right, key);
    fix(n);
    int slant = height_of(n->left) - height_of(n->right);
    if (slant > 1) {
        if (height_of(n->left->left) < height_of(n->left->right))
            n->left = rotate(n->left, false);
        return rotate(n, true);
    }
    if (slant < -1) {
        if (height_of(n->right->right) < height_of(n->right->left))
            n->right = rotate(n->right, true);
        return rotate(n, false);
    }
    return n;
}

class Node {
    public int Key;
    public int Height;
    public Node Left, Right;
    public Node(int key) { Key = key; }
}

static int Height(Node n) => n == null ? -1 : n.Height;

static void Fix(Node n) {
    n.Height = 1 + Math.Max(Height(n.Left), Height(n.Right));
}

static Node Rotate(Node n, bool toRight) {
    Node pivot = toRight ? n.Left : n.Right;
    if (toRight) { n.Left = pivot.Right; pivot.Right = n; }
    else { n.Right = pivot.Left; pivot.Left = n; }
    Fix(n);
    Fix(pivot);
    return pivot;
}

static Node Insert(Node n, int key) {
    if (n == null) return new Node(key);
    if (key < n.Key) n.Left = Insert(n.Left, key);
    else n.Right = Insert(n.Right, key);
    Fix(n);
    int slant = Height(n.Left) - Height(n.Right);
    if (slant > 1) {
        if (Height(n.Left.Left) < Height(n.Left.Right))
            n.Left = Rotate(n.Left, false);
        return Rotate(n, true);
    }
    if (slant < -1) {
        if (Height(n.Right.Right) < Height(n.Right.Left))
            n.Right = Rotate(n.Right, true);
        return Rotate(n, false);
    }
    return n;
}

static class Node {
    int key, height;
    Node left, right;

    Node(int key) { this.key = key; }
}

static int height(Node n) { return n == null ? -1 : n.height; }

static void fix(Node n) {
    n.height = 1 + Math.max(height(n.left), height(n.right));
}

static Node rotate(Node n, boolean toRight) {
    Node pivot = toRight ? n.left : n.right;
    if (toRight) { n.left = pivot.right; pivot.right = n; }
    else { n.right = pivot.left; pivot.left = n; }
    fix(n);
    fix(pivot);
    return pivot;
}

static Node insert(Node n, int key) {
    if (n == null) return new Node(key);
    if (key < n.key) n.left = insert(n.left, key);
    else n.right = insert(n.right, key);
    fix(n);
    int slant = height(n.left) - height(n.right);
    if (slant > 1) {
        if (height(n.left.left) < height(n.left.right))
            n.left = rotate(n.left, false);
        return rotate(n, true);
    }
    if (slant < -1) {
        if (height(n.right.right) < height(n.right.left))
            n.right = rotate(n.right, true);
        return rotate(n, false);
    }
    return n;
}