Balanced Tree

1 ─R→ 2 ─R→ 3 ─R→ 4 ─R→ 5

BF(node) = height(node.left) - height(node.right)

%%{init: {"flowchart": {"nodeSpacing": 16, "rankSpacing": 24, "padding": 8}}}%%
flowchart LR
  subgraph before["회전 전: LL"]
    direction TB
    b30["30"] -->|L| b20["20"]
    b20 -->|L| b10["10"]
  end
  subgraph after["회전 후"]
    direction TB
    a20["20"] -->|L| a10["10"]
    a20 -->|R| a30["30"]
  end
  before -.->|1| after

회전 전: y.left = x, x.right = 25
회전 후: x.right = y, y.left = 25
키 순서: 20 < 25 < 30

%%{init: {"flowchart": {"nodeSpacing": 16, "rankSpacing": 24, "padding": 8}}}%%
flowchart LR
  subgraph before["LR"]
    direction TB
    b30["30"] -->|L| b10["10"]
    b10 -->|R| b20["20"]
  end
  subgraph middle["LL"]
    direction TB
    m30["30"] -->|L| m20["20"]
    m20 -->|L| m10["10"]
  end
  subgraph after["균형 복구"]
    direction TB
    a20["20"] -->|L| a10["10"]
    a20 -->|R| a30["30"]
  end
  before -.->|1| middle
  middle -.->|2| after

빈자리까지 비교하며 내려감
→ 새 Leaf 생성
→ 자식의 새 Root를 연결
→ 현재 height 갱신
→ BF 확인과 필요한 회전
→ 이 부분 트리의 새 Root 반환

# AVL 트리 노드 정의와 높이 계산 — Node / get_height / get_balance
class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 0       # 리프의 높이는 0

def get_height(node):
    return node.height if node else -1   # 빈 트리는 -1

def get_balance(node):
    if node is None:
        return 0
    # 균형 인수 = 왼쪽 높이 - 오른쪽 높이
    return get_height(node.left) - get_height(node.right)

# AVL 회전 — rotate_right / rotate_left
def rotate_right(y):          # y가 왼쪽으로 무거울 때 (LL)
    x = y.left                # 왼쪽 자식을 위로 올린다
    y.left = x.right          # x의 오른쪽 서브트리를 y의 왼쪽으로 넘긴다
    x.right = y               # y를 x의 오른쪽 자식으로 내린다
    # 아래쪽 y부터 높이 갱신 (순서 중요)
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    x.height = 1 + max(get_height(x.left), get_height(x.right))
    return x                  # 새 부모 x를 돌려준다

def rotate_left(x):           # x가 오른쪽으로 무거울 때 (RR), 좌우 대칭
    y = x.right
    x.right = y.left
    y.left = x
    x.height = 1 + max(get_height(x.left), get_height(x.right))
    y.height = 1 + max(get_height(y.left), get_height(y.right))
    return y

# AVL 삽입 + 재균형 — insert()
def insert(node, key):
    if node is None:
        return Node(key)              # 빈 자리에 새 노드
    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    else:
        return node                   # 같은 키는 추가하지 않는다

    # 되돌아 올라오며 높이 갱신
    node.height = 1 + max(get_height(node.left), get_height(node.right))
    balance = get_balance(node)

    if balance > 1 and key < node.left.key:        # LL
        return rotate_right(node)
    if balance < -1 and key > node.right.key:      # RR
        return rotate_left(node)
    if balance > 1 and key > node.left.key:        # LR
        node.left = rotate_left(node.left)
        return rotate_right(node)
    if balance < -1 and key < node.right.key:      # RL
        node.right = rotate_right(node.right)
        return rotate_left(node)
    return node                                    # 균형 OK


def find(node, key):
    while node is not None and node.key != key:
        node = node.left if key < node.key else node.right
    return node


def verify(root, expected):
    """캐시를 믿지 않고 높이·순서·균형·노드 중복을 검사한다."""
    identities = {}

    def visit(node, low, high):
        if node is None:
            return -1, []
        assert id(node) not in identities
        identities[id(node)] = node.key
        assert low is None or low < node.key
        assert high is None or node.key < high
        left_height, left_keys = visit(node.left, low, node.key)
        right_height, right_keys = visit(node.right, node.key, high)
        actual_height = 1 + max(left_height, right_height)
        assert node.height == actual_height
        assert abs(left_height - right_height) <= 1
        return actual_height, left_keys + [node.key] + right_keys

    height, keys = visit(root, None, None)
    assert keys == expected
    return height, identities


def build_checked(values):
    root = None
    expected = []
    old_ids = {}
    for key in values:
        old_node = find(root, key)
        root = insert(root, key)  # 회전으로 바뀐 루트를 다시 받는다.
        if key not in expected:
            expected = sorted(expected + [key])
        _, new_ids = verify(root, expected)
        assert all(new_ids.get(identity) == value
                   for identity, value in old_ids.items())
        assert len(new_ids) - len(old_ids) == (1 if old_node is None else 0)
        if old_node is not None:
            assert find(root, key) is old_node
        old_ids = new_ids
    return root


def fixture(key, left=None, right=None):
    node = Node(key)
    node.left, node.right = left, right
    node.height = 1 + max(get_height(left), get_height(right))
    return node


def main():
    assert verify(None, [])[0] == -1 and find(None, 1) is None
    print("empty: height=-1; search missing")
    one = build_checked([7])
    assert one.height == 0
    print("single: root=7; height=0")

    for name, values in [("LL", [30, 20, 10]), ("RR", [10, 20, 30]),
                         ("LR", [30, 10, 20]), ("RL", [10, 30, 20])]:
        root = build_checked(values)
        assert (root.key, root.left.key, root.right.key, root.height) == (20, 10, 30, 1)
        print(f"{name}: root=20; height=1; inorder=[10, 20, 30]")

    root = build_checked([1, 2, 3, 4, 5])
    assert (root.key, root.left.key, root.right.key) == (2, 1, 4)
    assert (root.right.left.key, root.right.right.key, root.height) == (3, 5, 2)
    print("sorted 1..5: root=2; height=2; inorder=[1, 2, 3, 4, 5]")
    assert find(root, 4) is root.right and find(root, 6) is None
    print("search: 4 found; 6 missing")

    duplicates = build_checked([1, 1, 1])
    assert duplicates.key == 1 and duplicates.height == 0
    print("duplicates [1, 1, 1]: one existing node; height=0")
    build_checked([20, 10, 30, 5, 15, 25, 35, 10, 20, 30, 5])
    print("mixed duplicates: existing node identities preserved")
    build_checked(list(range(1, 32)))
    build_checked(list(range(31, 0, -1)))
    print("ascending/descending 31: invariants checked after every insertion")
    build_checked([0, -3, 8, -10, -1, 5, 12, 6, 7])
    print("mixed negative keys: order, heights and identities preserved")

    middle = fixture(25)
    five, ten, forty = fixture(5), fixture(10), fixture(40)
    ten.left, ten.height = five, 1
    x = fixture(20, ten, middle)
    y = fixture(30, x, forty)
    old_ids = {id(n): n.key for n in [five, ten, x, middle, y, forty]}
    new_root = rotate_right(y)
    assert new_root is x and new_root.right is y and y.left is middle
    assert verify(new_root, [5, 10, 20, 25, 30, 40])[1] == old_ids
    print("rotate_right: middle subtree 25 transferred; all six nodes preserved")

    middle = fixture(25)
    ten, forty_five = fixture(10), fixture(45)
    forty = fixture(40, None, forty_five)
    y = fixture(30, middle, forty)
    x = fixture(20, ten, y)
    old_ids = {id(n): n.key for n in [ten, x, middle, y, forty, forty_five]}
    new_root = rotate_left(x)
    assert new_root is y and new_root.left is x and x.right is middle
    assert verify(new_root, [10, 20, 25, 30, 40, 45])[1] == old_ids
    print("rotate_left: middle subtree 25 transferred; all six nodes preserved")
    print("all checks passed")


if __name__ == "__main__":
    main()

python3 avl-tree.py

empty: height=-1; search missing
single: root=7; height=0
LL: root=20; height=1; inorder=[10, 20, 30]
RR: root=20; height=1; inorder=[10, 20, 30]
LR: root=20; height=1; inorder=[10, 20, 30]
RL: root=20; height=1; inorder=[10, 20, 30]
sorted 1..5: root=2; height=2; inorder=[1, 2, 3, 4, 5]
search: 4 found; 6 missing
duplicates [1, 1, 1]: one existing node; height=0
mixed duplicates: existing node identities preserved
ascending/descending 31: invariants checked after every insertion
mixed negative keys: order, heights and identities preserved
rotate_right: middle subtree 25 transferred; all six nodes preserved
rotate_left: middle subtree 25 transferred; all six nodes preserved
all checks passed

N(-1) = 0
N(0) = 1
N(1) = 2
N(h) = 1 + N(h-1) + N(h-2)     (h >= 1)
높이 0, 1, 2, 3, 4의 최소 노드 수: 1, 2, 4, 7, 12

n + 1 >= F(h+3) >= φ^(h+1)
h <= log_φ(n+1) - 1
  = log₂(n+1) / log₂φ - 1
  ≈ 1.44042 × log₂(n+1) - 1

n >= 2^b - 1
b <= log₂(n + 1)
h + 1 <= 2b <= 2 log₂(n + 1)

RED, BLACK = 0, 1


class Node:
    def __init__(self, key, color=RED):
        self.key = key
        self.color = color
        self.left = None
        self.right = None
        self.parent = None


def color(node):
    return BLACK if node is None else node.color


def rotate_left(tree, x):
    y = x.right
    assert y is not None
    x.right = y.left
    if y.left is not None:
        y.left.parent = x
    y.parent = x.parent
    if x.parent is None:
        tree.root = y
    elif x is x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y
    y.left = x
    x.parent = y
    tree.rotations += 1


def rotate_right(tree, x):
    y = x.left
    assert y is not None
    x.left = y.right
    if y.right is not None:
        y.right.parent = x
    y.parent = x.parent
    if x.parent is None:
        tree.root = y
    elif x is x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y
    y.right = x
    x.parent = y
    tree.rotations += 1


def insert_fixup(tree, z):
    while color(z.parent) == RED:
        gp = z.parent.parent
        if z.parent is gp.left:
            uncle = gp.right
            if color(uncle) == RED:
                z.parent.color = BLACK
                uncle.color = BLACK
                gp.color = RED
                z = gp
            else:
                if z is z.parent.right:
                    z = z.parent
                    rotate_left(tree, z)
                z.parent.color = BLACK
                gp.color = RED
                rotate_right(tree, gp)
        else:
            uncle = gp.left
            if color(uncle) == RED:
                z.parent.color = BLACK
                uncle.color = BLACK
                gp.color = RED
                z = gp
            else:
                if z is z.parent.left:
                    z = z.parent
                    rotate_right(tree, z)
                z.parent.color = BLACK
                gp.color = RED
                rotate_left(tree, gp)
    tree.root.color = BLACK


class RBTree:
    def __init__(self):
        self.root = None
        self.rotations = 0

    def find(self, key):
        node = self.root
        while node is not None:
            if key == node.key:
                return node
            node = node.left if key < node.key else node.right
        return None

    def insert(self, key):
        parent, node = None, self.root
        while node is not None:
            parent = node
            if key == node.key:
                return node
            node = node.left if key < node.key else node.right
        new = Node(key)
        new.parent = parent
        if parent is None:
            self.root = new
        elif key < parent.key:
            parent.left = new
        else:
            parent.right = new
        insert_fixup(self, new)
        return new


# 아래 함수는 자료구조 연산과 별개로 실제 연결과 불변식을 검사한다.
def verify(tree, expected):
    keys, identities = [], {}

    def visit(node, parent, low, high):
        if node is None:
            return -1, 0  # 높이, NIL을 제외한 검정 높이
        assert id(node) not in identities
        identities[id(node)] = node.key
        assert node.parent is parent
        assert low is None or low < node.key
        assert high is None or node.key < high
        assert node.color in (RED, BLACK)
        if node.color == RED:
            assert node.left is None or node.left.color == BLACK
            assert node.right is None or node.right.color == BLACK
        lh, lb = visit(node.left, node, low, node.key)
        keys.append(node.key)
        rh, rb = visit(node.right, node, node.key, high)
        assert lb == rb
        return 1 + max(lh, rh), lb + (node.color == BLACK)

    if tree.root is not None:
        assert tree.root.color == BLACK and tree.root.parent is None
    height, black_height = visit(tree.root, None, None, None)
    assert keys == sorted(set(expected))
    assert len(keys) >= 2 ** black_height - 1
    assert height + 1 <= 2 * black_height
    return height, black_height, identities


def build_checked(values):
    tree, inserted, previous_ids, steps = RBTree(), [], {}, []
    for key in values:
        existing = tree.find(key)
        before = tree.rotations
        returned = tree.insert(key)
        steps.append(tree.rotations - before)
        assert steps[-1] <= 2
        if existing is not None:
            assert returned is existing and steps[-1] == 0
        inserted.append(key)
        height, bh, identities = verify(tree, inserted)
        assert all(identities.get(node_id) == value
                   for node_id, value in previous_ids.items())
        assert tree.find(key) is returned
        previous_ids = identities
    return tree, steps


def main():
    empty = RBTree()
    assert verify(empty, [])[:2] == (-1, 0)
    assert empty.find(7) is None
    print("empty: height=-1; black-height=0; search missing")
    single, _ = build_checked([7])
    assert verify(single, [7])[:2] == (0, 1)
    print("single: root=7 black; height=0; black-height=1")

    cases = [("LL", [30, 20, 10], 1), ("RR", [10, 20, 30], 1),
             ("LR", [30, 10, 20], 2), ("RL", [10, 30, 20], 2)]
    for name, values, count in cases:
        tree, steps = build_checked(values)
        assert tree.root.key == 20 and steps[-1] == count
        assert tree.root.left.color == RED and tree.root.right.color == RED
        print(f"{name}: root=20 black; last-insert rotations={count}")

    for side, values in [("left", [10, 5, 15, 1]),
                         ("right", [10, 5, 15, 20])]:
        tree, steps = build_checked(values)
        assert tree.root.key == 10 and steps[-1] == 0
        assert tree.root.left.color == tree.root.right.color == BLACK
        assert verify(tree, values)[:2] == (2, 2)
        print(f"red uncle ({side}): root=10 black; rotations=0; black-height=2")

    tree, _ = build_checked([41, 38, 31, 12, 19, 8])
    assert tree.find(19).key == 19 and tree.find(99) is None
    print("mixed insertion: 19 found; 99 missing; all invariants hold")
    for values in [range(1, 32), range(31, 0, -1)]:
        build_checked(values)
    print("ascending/descending 31: invariants and rotation bound checked per insertion")
    tree, _ = build_checked([1, 1, 1])
    assert len(verify(tree, [1])[2]) == 1
    build_checked([0, -3, 8, -10, -1, 5, 12, 6, 7, -3, 8, 0])
    print("duplicates and negative keys: existing nodes and parent links preserved")
    print("all checks passed")


if __name__ == "__main__":
    main()

empty: height=-1; black-height=0; search missing
single: root=7 black; height=0; black-height=1
LL: root=20 black; last-insert rotations=1
RR: root=20 black; last-insert rotations=1
LR: root=20 black; last-insert rotations=2
RL: root=20 black; last-insert rotations=2
red uncle (left): root=10 black; rotations=0; black-height=2
red uncle (right): root=10 black; rotations=0; black-height=2
mixed insertion: 19 found; 99 missing; all invariants hold
ascending/descending 31: invariants and rotation bound checked per insertion
duplicates and negative keys: existing nodes and parent links preserved
all checks passed