Деревья AVL — это самобалансирующиеся двоичные деревья поиска, которые поддерживают сбалансированную структуру, обеспечивая эффективные операции поиска, вставки и удаления. В этой статье мы рассмотрим несколько методов вставки дерева AVL, включая примеры кода для каждого подхода. К концу вы получите полное представление о различных методах поддержания баланса во время процесса введения.

Метод 1: рекурсивная вставка
Один из самых простых способов вставки узла в дерево AVL — использование рекурсивного подхода. Вот пример реализации на Python:

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1
def insert(root, key):
    if not root:
        return Node(key)
    elif key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    root.height = 1 + max(get_height(root.left), get_height(root.right))
    balance = get_balance(root)
    if balance > 1 and key < root.left.key:
        return rotate_right(root)
    if balance < -1 and key > root.right.key:
        return rotate_left(root)
    if balance > 1 and key > root.left.key:
        root.left = rotate_left(root.left)
        return rotate_right(root)
    if balance < -1 and key < root.right.key:
        root.right = rotate_right(root.right)
        return rotate_left(root)
    return root

Метод 2: итеративная вставка
В дополнение к рекурсивному подходу вставка в дерево AVL также может быть реализована итеративно с использованием цикла. Вот пример Python:

def insert(root, key):
    if not root:
        return Node(key)
    curr = root
    parent = None
    while curr:
        parent = curr
        if key < curr.key:
            curr = curr.left
        else:
            curr = curr.right
    if key < parent.key:
        parent.left = Node(key)
    else:
        parent.right = Node(key)
    # Update heights and perform rotations if necessary
    return root

Метод 3: Массовая вставка
Если вам нужно вставить несколько узлов в дерево AVL, метод массовой вставки может оптимизировать процесс за счет уменьшения количества необходимых вращений. Вот пример Python:

def bulk_insert(root, keys):
    for key in keys:
        root = insert(root, key)
    return root

В этой статье мы рассмотрели различные методы вставки дерева AVL, включая рекурсивные, итеративные и массовые методы вставки. Каждый метод имеет свои преимущества и подходит для разных сценариев. Реализуя эти методы в своих древовидных приложениях AVL, вы можете обеспечить эффективные и сбалансированные древовидные структуры, которые обеспечивают быстрые операции поиска и извлечения информации.