ONE DUDE`S BLOG
/media/3682283_0.webp

Реализация бинарного дерева поиска

10.09.2020
Реализация бинарного дерева поиска, insert, add, remove методов.
Это серия статей

Достаточно давно хотел реализовать АВЛ деревья, решил начать с чего-то более простого.

Описание

Бинарное дерево - дерево в котором каждый из узлов имеет не более 2 потомков. Бинарное дерево поиска, помимо выше сказанного, добавляет следующее описание: левые потомки должны быть меньше родительского элемента, правые больше. Данное условие снижает сложность алгоритма поиска до O(logn)

Перед реализацией разберем, какие же методы должны быть имплементированы.

  1. Поиск - достаточно простая операция, проверяем значение ключа, если оно меньше корня дерева - спускаемся ниже к левому ребенку и повторяем операцию для следующего узла, в случае если значение больше - спускаемся к правому, повторяем до тех пор, пока не найдем ключ, либо, до отсутствия у ноды дочерних узлов.
  2. Вставка - ищем узел, который будет родителем для вставляемого узла. После чего, если вставляемый ключ меньше чем ключ найденного элемента - создаем левый узел, в противном случае - правый.
  3. Удаление - наиболее сложный сценарий, существует 3 варианта удаления
    1. Наиболее простой сценарий удаления узла бинарного дерева. Если удаляемый узел не имеет потомков - просто затираем у родительского узла указатель на найденный элемент.
    2. Если у найденного узла имеется только 1 потомок, то присваиваем родительской ноде указатель на потомка.
    3. Если у найденного узла имеется 2 потомка, и левый узел правого поддерева отсутсвует, то копируем из правого узла указатель в найденный узел. Иначе, заменяем указатель текущей ноды на ноду правого узла, ищем минимальный элемент (всегда самый нижний левый) в правом поддереве, добавляем к нему левого потомка указывающего на левый потомок найденного элемента. Не забываем в первом левом узле указать родителя.

Наглядно

Реализация

Перед началом необходимо создать структуру дерева

type Node struct {
    key int
    left *Node
    right *Node
    parent *Node
}

Также реализуем метод выбора потомка (если ключ меньше родительского ключа - выбираем левое поддерево, если больше правое)

func (n *Node) selectNextNode(key int) **Node {
    if key < n.key {
        return &n.left
    }
    return &n.right
}

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

nextNode := lastNode.selectNextNode(key)
*nextNode = newNode

Вставка

Перед методом добавления создадим функцию для поиска наиболее подходящего узла

func (t *Node) findParentNode(key int) *Node {
    node := t
    for {
        if node.key == key {
            break
        }
        nodeAddr := node.selectNextNode(key)
        n := *nodeAddr
        if n == nil {
            break
        }
        node = n
    }
    return node
}

В данной функции, мы перебираем потомков, наиболее подходящих по ключу, до тех пор, пока не найдем узел у которого нет потомка. Следующий этап - непосредственно вставка

func (n *Node) Insert(key int) {
    newNode := &Node{
        key: key,
    }
    lastNode := n.findParentNode(key)
    if lastNode.key == key {
        return
    }
    newNode.parent = lastNode

    nextNode := lastNode.selectNextNode(key)
    *nextNode = newNode
}

Присваеваем новому узлу родителя последний подходящий узел. Получаем указатель на адрес, вставляемого элемента, перезаписываем адрес на текущей узел.

Разберем визуально на примере, допустим, мы хотим вставить ноду с ключем 26.

  1. Вызываем функцию поиска родительского узла (findParentNode)
    1. 26 < 42 => присваиваем в текущую ноду левый ребенок (22)
    2. 26 > 22 => присваимваем в текущую ноду правого ребенка
    3. 26 < 33 => присваиваем в текущую ноду левого ребенка
    4. 26 < 31 => присваем в текущую ноду левого ребенка
    5. левый ребенок nil, завершаем итерацию и возвращаем последнюю найденную ноду (31)
  2. 26 < ключа вернувшегося узла (31) => создаем левый узел у узла 31 c ключем 26.

На выходе у нас получается дерево (синим указан путь, который мы прошли выше):

Поиск

Поиск - наиболее тривиальный метод, если ключ равен искомому - возвращаем узел, если меньше вызываем рекурсивно функцию для левого потомка, в противном случае - для правого.

func (n *Node) Find(key int) *Node {
    if key == n.key {
        return n
    }

    if n.left != nil && key < n.key {
        return n.left.Find(key)
    }

    if n.right != nil && key > n.key {
        return n.right.Find(key)
    }
    return nil
}

Визуально проитерируемся по дереву указнному выше, попробуем найти ноду с ключем 98.

  1. 98 > 42 => устанавливаем текущую ноду правой
  2. 98 < 99 => устанавливаем текущую ноду левой
  3. 98 == 98, возвращаем текущую ноду

Визуально наш путь выглядит так:

Удаление

func (n *Node) Remove(key int) {
    if key < n.key {
        n.left.Remove(key)
        return
    }
    if key > n.key {
        n.right.Remove(key)
        return
    }

    nextNode := n.parent.selectNextNode(key)
    // Первый случай, у узла нет потомков
    if n.left == nil && n.right == nil {
        *nextNode = nil
        return
    }

    // Второй случай, у зла 1 потомок
    if n.left == nil {
        *nextNode = n.right
        n.right.parent = n.parent
        return
    }

    if n.right == nil {
        *nextNode = n.left
        n.left.parent = n.parent)
        return
    }

    // 3 случай, у удаляемого узла 2 потомка
    maxLeftNode := n.right
    for {
        if maxLeftNode.left == nil {
            break
        }
        maxLeftNode = n.right.left
    }

    maxLeftNode.left = n.left
    n.left.parent = maxLeftNode

    n.right.parent = n.parent
    *nextNode = n.right

}

Первый сценарий, в случае если у найденного узла нет потомков наиболее прост. Попробуем удалить узел с 98 ключем. Сначала находим нужный узел:

  1. 98 > 42 => устанавливаем текущий узел правым
  2. 98 < 99 => устанавливаем текущий узел левым
  3. 98 == 98 и дети отсутствуют
  4. Присваиваем левый указатель узла с ключем в 99 null

Удаление узла с 1 потомком. Давайте удалим узел с ключем 31 (добавленным выше).

  1. 31 < 42 => устанавливаем текущим узлом левый (33)
  2. 31 < 33 => устанавливаем текущий узел левый (31)
  3. У узла с ключем 31 1 левый потомок (добавленный в примере выше) это нода с ключем 26
  4. Заменяем левый указатель в родительском узле (33) на узел с ключем 26

Получается дерево следующего вида:

Наиболее сложный вариант, удаляем узел с 2 дочерними элементами. Возьмем для удаления узел 22.

Т.к. левые дети, всегда имеют меньший ключ чем правые, мы можем быть уверены, что левые потомки данного дерева меньше левых потомков правого дерева. Тоесть 11->9 имеют меньшее значение чем 33->26. Следовательно, мы можем заменить 22 на 33 и добавить к самомому левому потомку (26) указатель на 11. Алгоритм следующий:

  1. 22 < 42 => текущий узел левый (22)
  2. 22 == 22 и имеет 2 детей;
  3. Заменяем 22 на 33 и находим максимальный левый узел в правой ноде узла 22, это 26.
  4. У узла 11 указываем родителя 26, у узла 26 указываем левого ребенка 11

Получается дерево следующего вида

Материала получилось много, в следующий раз попробуем отбалансировать наше дерево. Потыкать пример можно тут, Загрузить исходник можно на гитхабе

алгоритмы
Деревья
2
147