AVL Tree (עץ AVL)

1class Node:2    def __init__(self, key):3        self.key = key4        self.left = None5        self.right = None6        self.height = 17
8
9def height(node):10    return node.height if node else 011
12
13def update(node):14    node.height = 1 + max(height(node.left), height(node.right))15
16
17def rotate_right(y):18    x = y.left19    y.left = x.right20    x.right = y21    update(y)22    update(x)23    return x24
25
26def rotate_left(x):27    y = x.right28    x.right = y.left29    y.left = x30    update(x)31    update(y)32    return y33
34
35def insert(node, key):36    if node is None:37        return Node(key)38    if key < node.key:39        node.left = insert(node.left, key)40    else:41        node.right = insert(node.right, key)42    update(node)43    balance = height(node.left) - height(node.right)44    # Four imbalance cases: LL, RR, LR, RL45    if balance > 1 and key < node.left.key:46        return rotate_right(node)47    if balance < -1 and key > node.right.key:48        return rotate_left(node)49    if balance > 1:50        node.left = rotate_left(node.left)51        return rotate_right(node)52    if balance < -1:53        node.right = rotate_right(node.right)54        return rotate_left(node)55    return node56
57
58def inorder(node):59    if node is None:60        return []61    return inorder(node.left) + [node.key] + inorder(node.right)62
63
64root = None65for key in [10, 20, 30, 40, 50, 25]:66    root = insert(root, key)67
68print("Inorder:", inorder(root))69print("Root:", root.key, "| tree height:", root.height)

1class Node {2    constructor(key) {3        this.key = key;4        this.left = null;5        this.right = null;6        this.height = 1;7    }8}9
10const height = (n) => (n ? n.height : 0);11const update = (n) => {12    n.height = 1 + Math.max(height(n.left), height(n.right));13};14const balance = (n) => height(n.left) - height(n.right);15
16function rotateRight(y) {17    const x = y.left;18    y.left = x.right;19    x.right = y;20    update(y);21    update(x);22    return x;23}24
25function rotateLeft(x) {26    const y = x.right;27    x.right = y.left;28    y.left = x;29    update(x);30    update(y);31    return y;32}33
34function insert(node, key) {35    if (!node) return new Node(key);36    if (key < node.key) node.left = insert(node.left, key);37    else node.right = insert(node.right, key);38    update(node);39    const b = balance(node);40    // Four rebalancing cases: LL, RR, LR, RL41    if (b > 1 && key < node.left.key) return rotateRight(node);42    if (b < -1 && key > node.right.key) return rotateLeft(node);43    if (b > 1) {44        node.left = rotateLeft(node.left);45        return rotateRight(node);46    }47    if (b < -1) {48        node.right = rotateRight(node.right);49        return rotateLeft(node);50    }51    return node;52}53
54function inorder(node, out = []) {55    if (!node) return out;56    inorder(node.left, out);57    out.push(node.key);58    inorder(node.right, out);59    return out;60}61
62let root = null;63for (const key of [10, 20, 30, 40, 50, 25]) root = insert(root, key);64console.log("Root after rebalancing:", root.key);65console.log("Inorder:", inorder(root).join(" "));

1public class Main {2    static class Node {3        int key, height = 1;4        Node left, right;5        Node(int key) { this.key = key; }6    }7
8    static int height(Node n) { return n == null ? 0 : n.height; }9    static int balance(Node n) { return n == null ? 0 : height(n.left) - height(n.right); }10    static void update(Node n) { n.height = 1 + Math.max(height(n.left), height(n.right)); }11
12    static Node rotateRight(Node y) {13        Node x = y.left;14        y.left = x.right;15        x.right = y;16        update(y); update(x);17        return x;18    }19
20    static Node rotateLeft(Node x) {21        Node y = x.right;22        x.right = y.left;23        y.left = x;24        update(x); update(y);25        return y;26    }27
28    static Node insert(Node node, int key) {29        if (node == null) return new Node(key);30        if (key < node.key) node.left = insert(node.left, key);31        else node.right = insert(node.right, key);32        update(node);33        int b = balance(node);34        // Four imbalance cases: LL, RR, LR, RL35        if (b > 1 && key < node.left.key) return rotateRight(node);36        if (b < -1 && key > node.right.key) return rotateLeft(node);37        if (b > 1) { node.left = rotateLeft(node.left); return rotateRight(node); }38        if (b < -1) { node.right = rotateRight(node.right); return rotateLeft(node); }39        return node;40    }41
42    static void inorder(Node n, StringBuilder sb) {43        if (n == null) return;44        inorder(n.left, sb);45        sb.append(n.key).append(" ");46        inorder(n.right, sb);47    }48
49    public static void main(String[] args) {50        Node root = null;51        int[] keys = {10, 20, 30, 40, 50, 25};52        for (int k : keys) root = insert(root, k);53        StringBuilder sb = new StringBuilder();54        inorder(root, sb);55        System.out.println("Inorder: " + sb.toString().trim());56        System.out.println("Root after rebalancing: " + root.key + " (height " + root.height + ")");57    }58}

1#include <algorithm>2#include <iostream>3
4struct Node {5    int value;6    int height = 1;7    Node* left = nullptr;8    Node* right = nullptr;9    explicit Node(int v) : value(v) {}10};11
12int height(const Node* n) { return n ? n->height : 0; }13int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }14void updateHeight(Node* n) {15    n->height = 1 + std::max(height(n->left), height(n->right));16}17
18Node* rotateRight(Node* y) {19    Node* x = y->left;20    y->left = x->right;21    x->right = y;22    updateHeight(y);23    updateHeight(x);24    return x;25}26
27Node* rotateLeft(Node* x) {28    Node* y = x->right;29    x->right = y->left;30    y->left = x;31    updateHeight(x);32    updateHeight(y);33    return y;34}35
36Node* insert(Node* node, int value) {37    if (node == nullptr) return new Node(value);38    if (value < node->value) node->left = insert(node->left, value);39    else node->right = insert(node->right, value);40    updateHeight(node);41    int balance = balanceFactor(node);42    // Four rebalancing cases: LL, RR, LR, RL43    if (balance > 1 && value < node->left->value) return rotateRight(node);44    if (balance < -1 && value > node->right->value) return rotateLeft(node);45    if (balance > 1) {46        node->left = rotateLeft(node->left);47        return rotateRight(node);48    }49    if (balance < -1) {50        node->right = rotateRight(node->right);51        return rotateLeft(node);52    }53    return node;54}55
56void inorder(const Node* n) {57    if (n == nullptr) return;58    inorder(n->left);59    std::cout << n->value << "(h" << n->height << ") ";60    inorder(n->right);61}62
63int main() {64    Node* root = nullptr;65    for (int value : {10, 20, 30, 40, 50, 25}) root = insert(root, value);66    std::cout << "Root after rebalancing: " << root->value << "\n";67    std::cout << "In-order: ";68    inorder(root);69    std::cout << "\n";70    return 0;71}

1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5    int value, height;6    struct Node* left;7    struct Node* right;8} Node;9
10int height(const Node* n) { return n ? n->height : 0; }11int balanceFactor(const Node* n) { return height(n->left) - height(n->right); }12int maxInt(int a, int b) { return a > b ? a : b; }13
14Node* newNode(int value) {15    Node* n = calloc(1, sizeof(Node));16    n->value = value;17    n->height = 1;18    return n;19}20
21void updateHeight(Node* n) {22    n->height = 1 + maxInt(height(n->left), height(n->right));23}24
25Node* rotateRight(Node* y) {26    Node* x = y->left;27    y->left = x->right;28    x->right = y;29    updateHeight(y);30    updateHeight(x);31    return x;32}33
34Node* rotateLeft(Node* x) {35    Node* y = x->right;36    x->right = y->left;37    y->left = x;38    updateHeight(x);39    updateHeight(y);40    return y;41}42
43Node* insert(Node* node, int value) {44    if (node == NULL) return newNode(value);45    if (value < node->value) node->left = insert(node->left, value);46    else node->right = insert(node->right, value);47    updateHeight(node);48    int balance = balanceFactor(node);49    // Four rebalancing cases: LL, RR, LR, RL50    if (balance > 1 && value < node->left->value) return rotateRight(node);51    if (balance < -1 && value > node->right->value) return rotateLeft(node);52    if (balance > 1) {53        node->left = rotateLeft(node->left);54        return rotateRight(node);55    }56    if (balance < -1) {57        node->right = rotateRight(node->right);58        return rotateLeft(node);59    }60    return node;61}62
63void inorder(const Node* n) {64    if (n == NULL) return;65    inorder(n->left);66    printf("%d(h%d) ", n->value, n->height);67    inorder(n->right);68}69
70int main(void) {71    int values[] = {10, 20, 30, 40, 50, 25};72    Node* root = NULL;73    for (int i = 0; i < 6; i++) root = insert(root, values[i]);74    printf("Root after rebalancing: %d\n", root->value);75    printf("In-order: ");76    inorder(root);77    printf("\n");78    return 0;79}