Алгоритмы и структуры данных для начинающих: двоичное дерево поиска

До сих пор мы рассматривали структуры данных, данные в которых располагаются линейно. В связном списке — от первого узла к единственному последнему. В динамическом массиве — в виде непрерывного блока.

В этой части мы рассмотрим совершенно новую структуру данных — дерево. А точнее, двоичное (бинарное) дерево поиска (binary search tree). Бинарное дерево поиска имеет структуру дерева, но элементы в нем расположены по определенным правилам.

Также смотрите другие материалы этой серии: стеки и очереди, динамический массив, связный список, оценка сложности алгоритма, сортировка и множества.

Для начала мы рассмотрим обычное дерево.

Деревья

Дерево — это структура, в которой у каждого узла может быть ноль или более подузлов — «детей». Например, дерево может выглядеть так:

Структура организации

Это дерево показывает структуру компании. Узлы представляют людей или подразделения, линии — связи и отношения. Дерево — это самый эффективный способ представления и хранения такой информации.

Дерево на картинке выше очень простое. Оно отражает только отношение родства категорий, но не накладывает никаких ограничений на свою структуру. У генерального директора может быть как один непосредственный подчиненный, так и несколько или ни одного. На рисунке отдел продаж находится левее отдела маркетинга, но порядок на самом деле не имеет значения. Единственное ограничение дерева — каждый узел может иметь не более одного родителя. Самый верхний узел (совет директоров, в нашем случае) родителя не имеет. Этот узел называется «корневым», или «корнем».

Двоичное дерево поиска

Двоичное дерево поиска похоже на дерево из примера выше, но строится по определенным правилам:

У каждого узла не более двух детей.
Любое значение меньше значения узла становится левым ребенком или ребенком левого ребенка.
Любое значение больше или равное значению узла становится правым ребенком или ребенком правого ребенка.

Давайте посмотрим на дерево, построенное по этим правилам:

Двоичное дерево поиска

Обратите внимание, как указанные ограничения влияют на структуру дерева. Каждое значение слева от корня (8) меньше восьми, каждое значение справа — больше либо равно корню. Это правило применимо к любому узлу дерева.

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

Мы не знаем точно, в каком порядке добавлялись остальные значения, но можем представить один из возможных путей. Узлы добавляются методом Add, который принимает добавляемое значение.

BinaryTree tree = new BinaryTree();
tree.Add(8);
tree.Add(4);
tree.Add(2);
tree.Add(3);
tree.Add(10);
tree.Add(6);
tree.Add(7);

Рассмотрим подробнее первые шаги.

В первую очередь добавляется 8. Это значение становится корнем дерева. Затем мы добавляем 4. Поскольку 4 меньше 8, мы кладем ее в левого ребенка, согласно правилу 2. Поскольку у узла с восьмеркой нет детей слева, 4 становится единственным левым ребенком.

После этого мы добавляем 2. 2 меньше 8, поэтому идем налево. Так как слева уже есть значение, сравниваем его со вставляемым. 2 меньше 4, а у четверки нет детей слева, поэтому 2 становится левым ребенком 4.

Затем мы добавляем тройку. Она идет левее 8 и 4. Но так как 3 больше, чем 2, она становится правым ребенком 2, согласно третьему правилу.

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

Класс `BinaryTreeNode`

Класс BinaryTreeNode представляет один узел двоичного дерева. Он содержит ссылки на левое и правое поддеревья (если поддерева нет, ссылка имеет значение null), данные узла и метод IComparable.CompareTo для сравнения узлов. Он пригодится для определения, в какое поддерево должен идти данный узел. Как видите, класс BinaryTreeNode очень простой:

class BinaryTreeNode : IComparable
    where TNode : IComparable
{
    public BinaryTreeNode(TNode value)
    {
        Value = value;
    }
 
    public BinaryTreeNode Left { get; set; }
    public BinaryTreeNode Right { get; set; }
    public TNode Value { get; private set; }
 
    /// 
    /// Сравнивает текущий узел с данным.
    /// 
    /// Сравнение производится по полю Value.
    /// Метод возвращает 1, если значение текущего узла больше,
    /// чем переданного методу, -1, если меньше и 0, если они равны
    public int CompareTo(TNode other)
    {
        return Value.CompareTo(other);
    }
}

Класс `BinaryTree`

Класс BinaryTree предоставляет основные методы для манипуляций с данными: вставка элемента (Add), удаление (Remove), метод Contains для проверки, есть ли такое значение в дереве, несколько методов для обхода дерева различными способами, метод Count и Clear.

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

public class BinaryTree : IEnumerable
    where T : IComparable
{
    private  BinaryTreeNode _head;
    private int _count;
 
    public void Add(T value)
    {
        throw new NotImplementedException();
    }
 
    public bool Contains(T value)
    {
        throw new NotImplementedException();
    }
 
    public bool Remove(T value)
    {
        throw new NotImplementedException();
    }
 
    public void PreOrderTraversal(Action action)
    {
        throw new NotImplementedException();
    }
 
    public void PostOrderTraversal(Action action)
    {
        throw new NotImplementedException();
    }
 
    public void InOrderTraversal(Action action)
    {
        throw new NotImplementedException();
    }
 
    public IEnumerator GetEnumerator()
    {
        throw new NotImplementedException();
    }
 
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        throw new NotImplementedException();
    }
 
    public void Clear()
    {
        throw new NotImplementedException();
    }
 
    public int Count
    {
        get;
    }
}

Метод `Add`

Поведение: Добавляет элемент в дерево на корректную позицию.
Сложность: O(log n) в среднем; O(n) в худшем случае.

Добавление узла не представляет особой сложности. Оно становится еще проще, если решать эту задачу рекурсивно. Есть всего два случая, которые надо учесть:

Дерево пустое.
Дерево не пустое.

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

public void Add(T value)
{
    // Случай 1: Если дерево пустое, просто создаем корневой узел.
    if (_head == null)
    {
        _head = new BinaryTreeNode(value);
    }
    // Случай 2: Дерево не пустое => 
    // ищем правильное место для вставки.
    else
    {
        AddTo(_head, value);
    }
 
    _count++;
}
 
// Рекурсивная ставка.
private void AddTo(BinaryTreeNode node, T value)
{
    // Случай 1: Вставляемое значение меньше значения узла
    if (value.CompareTo(node.Value) < 0)
    {
        // Если нет левого поддерева, добавляем значение в левого ребенка,
        if (node.Left == null)
        {
            node.Left = new BinaryTreeNode(value);
        }
        else
        {
            // в противном случае повторяем для левого поддерева.
            AddTo(node.Left, value);
        }
    }
    // Случай 2: Вставляемое значение больше или равно значению узла.
    else
    {
        // Если нет правого поддерева, добавляем значение в правого ребенка,
        if (node.Right == null)
        {
            node.Right = new BinaryTreeNode(value);
        }
        else
        {
            // в противном случае повторяем для правого поддерева.
            AddTo(node.Right, value);
        }
    }
}

Метод `Remove`

Поведение: Удаляет первый узел с заданным значением.
Сложность: O(log n) в среднем; O(n) в худшем случае.

Удаление узла из дерева — одна из тех операций, которые кажутся простыми, но на самом деле таят в себе немало подводных камней.

В целом, алгоритм удаления элемента выглядит так:

Найти узел, который надо удалить.
Удалить его.

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

Случай 1: У удаляемого узла нет правого ребенка.

В этом случае мы просто перемещаем левого ребенка (при его наличии) на место удаляемого узла. В результате дерево будет выглядеть так:

Случай 2: У удаляемого узла есть только правый ребенок, у которого, в свою очередь нет левого ребенка.

В этом случае нам надо переместить правого ребенка удаляемого узла (6) на его место. После удаления дерево будет выглядеть так:

Случай 3: У удаляемого узла есть первый ребенок, у которого есть левый ребенок.

В этом случае место удаляемого узла занимает крайний левый ребенок правого ребенка удаляемого узла.

Давайте посмотрим, почему это так. Мы знаем о поддереве, начинающимся с удаляемого узла следующее:

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

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

После удаления узла дерево будет выглядеть так:

Теперь, когда мы знаем, как удалять узлы, посмотрим на код, который реализует этот алгоритм.

Отметим, что метод FindWithParent (см. метод Contains) возвращает найденный узел и его родителя, поскольку мы должны заменить левого или правого ребенка родителя удаляемого узла.

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

public bool Remove(T value)
{
    BinaryTreeNode current, parent;
 
    // Находим удаляемый узел.
    current = FindWithParent(value, out parent);
 
    if (current == null)
    {
        return false;
    }
 
    _count--;
 
    // Случай 1: Если нет детей справа, левый ребенок встает на место удаляемого.
    if (current.Right == null)
    {
        if (parent == null)
        {
            _head = current.Left;
        }
        else
        {
            int result = parent.CompareTo(current.Value);
            if (result > 0)
            {
                // Если значение родителя больше текущего,
                // левый ребенок текущего узла становится левым ребенком родителя.
                parent.Left = current.Left;
            }
            else if (result < 0) { // Если значение родителя меньше текущего, // левый ребенок текущего узла становится правым ребенком родителя. parent.Right = current.Left; } } } // Случай 2: Если у правого ребенка нет детей слева // то он занимает место удаляемого узла. else if (current.Right.Left == null) { current.Right.Left = current.Left; if (parent == null) { _head = current.Right; } else { int result = parent.CompareTo(current.Value); if (result > 0)
            {
                // Если значение родителя больше текущего,
                // правый ребенок текущего узла становится левым ребенком родителя.
                parent.Left = current.Right;
            }
            else if (result < 0) { // Если значение родителя меньше текущего, // правый ребенок текущего узла становится правым ребенком родителя. parent.Right = current.Right; } } } // Случай 3: Если у правого ребенка есть дети слева, крайний левый ребенок // из правого поддерева заменяет удаляемый узел. else { // Найдем крайний левый узел. BinaryTreeNode leftmost = current.Right.Left; BinaryTreeNode leftmostParent = current.Right; while (leftmost.Left != null) { leftmostParent = leftmost; leftmost = leftmost.Left; } // Левое поддерево родителя становится правым поддеревом крайнего левого узла. leftmostParent.Left = leftmost.Right; // Левый и правый ребенок текущего узла становится левым и правым ребенком крайнего левого. leftmost.Left = current.Left; leftmost.Right = current.Right; if (parent == null) { _head = leftmost; } else { int result = parent.CompareTo(current.Value); if (result > 0)
            {
                // Если значение родителя больше текущего,
                // крайний левый узел становится левым ребенком родителя.
                parent.Left = leftmost;
            }
            else if (result < 0)
            {
                // Если значение родителя меньше текущего,
                // крайний левый узел становится правым ребенком родителя.
                parent.Right = leftmost;
            }
        }
    }
 
    return true;
}

Метод `Contains`

Поведение: Возвращает true если значение содержится в дереве. В противном случает возвращает false.
Сложность: O(log n) в среднем; O(n) в худшем случае.

Метод Contains выполняется с помощью метода FindWithParent, который проходит по дереву, выполняя в каждом узле следующие шаги:

Если текущий узел null, вернуть null.
Если значение теккущего узна равно искомому, вернуть текущий узел.
Если искомое значение меньше значения текущего узла, установить левого ребенка текущим узлом и перейти к шагу 1.
В противном случае, установить правого ребенка текущим узлом и перейти к шагу 1.

Поскольку Contains возвращает булево значение, оно определяется сравнением результата выполнения FindWithParent с null. Если FindWithParent вернул непустой узел, Contains возвращает true.

Метод FindWithParent также используется в методе Remove.

public bool Contains(T value)
{
    // Поиск узла осуществляется другим методом.
    BinaryTreeNode parent;
    return FindWithParent(value, out parent) != null;
}
 
/// 
/// Находит и возвращает первый узел с заданным значением. Если значение
/// не найдено, возвращает null. Также возвращает родителя найденного узла (или null)
/// для использования в методе Remove.
/// 
private BinaryTreeNode FindWithParent(T value, out BinaryTreeNode parent)
{
    // Попробуем найти значение в дереве.
    BinaryTreeNode current = _head;
    parent = null;
 
    // До тех пор, пока не нашли...
    while (current != null)
    {
        int result = current.CompareTo(value);
 
        if (result > 0)
        {
            // Если искомое значение меньше, идем налево.
            parent = current;
            current = current.Left;
        }
        else if (result < 0)
        {
            // Если искомое значение больше, идем направо.
            parent = current;
            current = current.Right;
        }
        else
        {
            // Если равны, то останавливаемся
            break;
        }
    }
 
    return current;
}

Метод `Count`

Поведение: Возвращает количество узлов дерева или 0, если дерево пустое.
Сложность: O(1)

Это поле инкрементируется методом Add и декрементируется методом Remove.

public int Count
{
    get
    {
        return _count;
    }
}

Метод `Clear`

Поведение: Удаляет все узлы дерева.
Сложность: O(1)

public void Clear()
{
    _head = null;
    _count = 0;
}

Обход деревьев

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

Пример дерева для обхода

Методы обхода в примерах будут принимать параметр Action<T>, который определяет действие, поизводимое над каждым узлом.

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

Метод `Preorder` (или префиксный обход)

Поведение: Обходит дерево в префиксном порядке, выполняя указанное действие над каждым узлом.
Сложность: O(n)
Порядок обхода: 4, 2, 1, 3, 5, 7, 6, 8

При префиксном обходе алгоритм получает значение текущего узла перед тем, как перейти сначала в левое поддерево, а затем в правое. Начиная от корня, сначала мы получим значение 4. Затем таким же образом обходятся левый ребенок и его дети, затем правый ребенок и все его дети.

Префиксный обход обычно применяется для копирования дерева с сохранением его структуры.

public void PreOrderTraversal(Action action)
{
    PreOrderTraversal(action, _head);
}
 
private void PreOrderTraversal(Action action, BinaryTreeNode node)
{
    if (node != null)
    {
        action(node.Value);
        PreOrderTraversal(action, node.Left);
        PreOrderTraversal(action, node.Right);
    }
}

Метод `Postorder` (или постфиксный обход)

Поведение: Обходит дерево в префиксном порядке, выполняя указанное действие над каждым узлом.
Сложность: O(n)
Порядок обхода: 1, 3, 2, 6, 8, 7, 5, 4

При постфиксном обходе мы посещаем левое поддерево, правое поддерево, а потом, после обхода всех детей, переходим к самому узлу.

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

public void PostOrderTraversal(Action action)
{
    PostOrderTraversal(action, _head);
}
 
private void PostOrderTraversal(Action action, BinaryTreeNode node)
{
    if (node != null)
    {
        PostOrderTraversal(action, node.Left);
        PostOrderTraversal(action, node.Right);
        action(node.Value);
    }
}

Метод `Inorder` (или инфиксный обход)

Поведение: Обходит дерево в инфиксном порядке, выполняя указанное действие над каждым узлом.
Сложность: O(n)
Порядок обхода: 1, 2, 3, 4, 5, 6, 7, 8

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

В примере ниже показаны два способа инфиксного обхода. Первый — рекурсивный. Он выполняет указанное действие с каждым узлом. Второй использует стек и возвращает итератор для непосредственного перебора.

Public void InOrderTraversal(Action action)
{
    InOrderTraversal(action, _head);
}
 
private void InOrderTraversal(Action action, BinaryTreeNode node)
{
    if (node != null)
    {
        InOrderTraversal(action, node.Left);
 
        action(node.Value);
 
        InOrderTraversal(action, node.Right);
    }
}
 
public IEnumerator InOrderTraversal()
{
    // Это нерекурсивный алгоритм.
    // Он использует стек для того, чтобы избежать рекурсии.
    if (_head != null)
    {
        // Стек для сохранения пропущенных узлов.
        Stack stack = new Stack();
 
        BinaryTreeNode current = _head;

        // Когда мы избавляемся от рекурсии, нам необходимо
        // запоминать, в какую стороны мы должны двигаться.
        bool goLeftNext = true;
 
        // Кладем в стек корень.
        stack.Push(current);
 
        while (stack.Count > 0)
        {
            // Если мы идем налево...
            if (goLeftNext)
            {
                // Кладем все, кроме самого левого узла на стек.
                // Крайний левый узел мы вернем с помощю yield.
                while (current.Left != null)
                {
                    stack.Push(current);
                    current = current.Left;
                }
            }
 
            // Префиксный порядок: left->yield->right.
            yield return current.Value;
 
            // Если мы можем пойти направо, идем.
            if (current.Right != null)
            {
                current = current.Right;
 
                // После того, как мы пошли направо один раз,
                // мы должным снова пойти налево.
                goLeftNext = true;
            }
            else
            {
                // Если мы не можем пойти направо, мы должны достать родительский узел
                // со стека, обработать его и идти в его правого ребенка.
                current = stack.Pop();
                goLeftNext = false;
            }
        }
    }
}

Метод `GetEnumerator`

Поведение: Возвращает итератор для обхода дерева инфиксным способом.
Сложность: Получение итератора — O(1). Обход дерева — O(n).

public IEnumerator GetEnumerator()
{
    return InOrderTraversal();
}
 
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
    return GetEnumerator();
}

Продолжение следует

На этом мы заканчивает пятую часть руководства по алгоритмам и структурам данных. В следующей статье мы рассмотрим множества (Set).

_{Перевод статьи «The Binary Search Tree»}

Как Яндекс использует ваши данные и машинное обучение для персонализации сервисов — читать и смотреть YaC 2019.

Алгоритмы и структуры данных для начинающих: двоичное дерево поиска

Деревья

Двоичное дерево поиска

Класс `BinaryTreeNode`

Класс `BinaryTree`

Метод `Add`

Метод `Remove`

Метод `Contains`

Метод `Count`

Метод `Clear`

Обход деревьев

Метод `Preorder` (или префиксный обход)

Метод `Postorder` (или постфиксный обход)

Метод `Inorder` (или инфиксный обход)

Метод `GetEnumerator`

Продолжение следует

Вакансии в тему:

Спасибо!

Теперь редакторы в курсе.

Алгоритмы и структуры данных для начинающих: двоичное дерево поиска

Деревья

Двоичное дерево поиска

Класс BinaryTreeNode

Класс BinaryTree

Метод Add

Метод Remove

Метод Contains

Метод Count

Метод Clear

Обход деревьев

Метод Preorder (или префиксный обход)

Метод Postorder (или постфиксный обход)

Метод Inorder (или инфиксный обход)

Метод GetEnumerator

Продолжение следует

Вакансии в тему:

Также рекомендуем:

Спасибо!

Теперь редакторы в курсе.

Класс `BinaryTreeNode`

Класс `BinaryTree`

Метод `Add`

Метод `Remove`

Метод `Contains`

Метод `Count`

Метод `Clear`

Метод `Preorder` (или префиксный обход)

Метод `Postorder` (или постфиксный обход)

Метод `Inorder` (или инфиксный обход)

Метод `GetEnumerator`