BST, AVL, Red-Black — unbalanced হলে কী হয়

import random


class AVLNode:
    __slots__ = ('key', 'left', 'right', 'h')

    def __init__(self, key):
        self.key, self.left, self.right, self.h = key, None, None, 1


def height(x):
    return x.h if x else 0

def update(x):
    x.h = 1 + max(height(x.left), height(x.right))

def bf(x):
    return height(x.left) - height(x.right)


def rotate_right(y):
    x = y.left
    y.left = x.right          # x-এর ডান subtree y-এর বাঁয়ে
    x.right = y               # y নামল x-এর ডানে
    update(y); update(x)      # নিচেরটা আগে!
    return x

def rotate_left(x):
    y = x.right
    x.right = y.left
    y.left = x
    update(x); update(y)
    return y


def rebalance(x):
    """ফেরার পথে; প্রথম imbalance-এ fix, নতুন subtree-root ফেরত"""
    update(x)
    b = bf(x)
    if b > 1:                                # বাঁয়ে ভারী
        if bf(x.left) \< 0:                  # LR: আগে বাঁক সোজা
            x.left = rotate_left(x.left)
        return rotate_right(x)                # LL
    if b \< -1:                               # ডানে ভারী
        if bf(x.right) > 0:                  # RL
            x.right = rotate_right(x.right)
        return rotate_left(x)                 # RR
    return x                                  # সুস্থ — ছোঁয়াইনি


def avl_insert(node, key):
    if not node:
        return AVLNode(key)
    if key \< node.key:
        node.left = avl_insert(node.left, key)
    elif key > node.key:
        node.right = avl_insert(node.right, key)
    else:
        return node                            # duplicate — কিছুই না
    return rebalance(node)


# ---------- validator: safety net ----------
def validate(node, lo=float('-inf'), hi=float('inf')):
    """subtree height ফেরত; পথে সব invariant assert"""
    if not node:
        return 0
    assert lo \< node.key \< hi, f'BST order ভাঙল @ {node.key}'
    hl = validate(node.left, lo, node.key)
    hr = validate(node.right, node.key, hi)
    assert node.h == 1 + max(hl, hr), f'height field ভুল @ {node.key}'
    assert abs(hl - hr) \<= 1, f'balance ভাঙল @ {node.key} ({hl}/{hr})'
    return node.h


if __name__ == '__main__':
    # --- টেস্ট ১: adversarial sorted input ---
    root = None
    for k in range(1, 16):
        root = avl_insert(root, k)
        validate(root)                         # প্রতি step-এ পূর্ণ audit
    print('sorted 1..15 OK, height =', height(root),
          '(perfect-এর কাছাকাছি: best =', len(range(1,16)).bit_length() - 2, ')')

    # --- টেস্ট ২: random ৫০০ insert ---
    root = None
    for k in random.sample(range(10_000), 500):
        root = avl_insert(root, k)
        validate(root)
    print('random 500 OK, height =', height(root),
          '(bound:', round(1.44 * 9), ')')

    # --- টেস্ট ৩: duplicate ---
    before = height(root)
    root = avl_insert(root, root.key)
    validate(root)
    assert height(root) == before
    print('duplicate insert OK — কোনো পরিবর্তন নেই')

প্রত্যাশিত output (random height seedভেদে ৯–১১):

sorted 1..15 OK, height = 4 (perfect-এর কাছাকাছি: best = 3 )
random 500 OK, height = 10 (bound: 13)
duplicate insert OK — কোনো পরিবর্তন নেই

(build-এর height field leaf-কে 1 গোনে — node-counting; experiment- এর stats edge-counting — তাই sorted tree এখানে ‘4’, ওখানে ‘3’।)

নিজে বাড়ান: (১) delete(key) — successor-swap + ফেরার পথে rebalance, rotation-count counter-সহ; (২) sorted vs random rotation- তুলনা; (৩) update() comment-out করে validator-কে ভাঙুন।