До сих пор мы рассматривали структуры данных, данные в которых располагаются линейно. В связном списке — от первого узла к единственному последнему. В динамическом массиве — в виде непрерывного блока.
В этой части мы рассмотрим совершенно новую структуру данных — дерево. А точнее, двоичное (бинарное) дерево поиска (binary search tree). Бинарное дерево поиска имеет структуру дерева, но элементы в нем расположены по определенным правилам.
Также смотрите другие материалы этой серии: стеки и очереди, динамический массив, связный список, оценка сложности алгоритма, сортировка и множества.
Для начала мы рассмотрим обычное дерево.
Деревья
Дерево — это структура, в которой у каждого узла может быть ноль или более подузлов — «детей». Например, дерево может выглядеть так:
Структура организации
Это дерево показывает структуру компании. Узлы представляют людей или подразделения, линии — связи и отношения. Дерево — это самый эффективный способ представления и хранения такой информации.
Дерево на картинке выше очень простое. Оно отражает только отношение родства категорий, но не накладывает никаких ограничений на свою структуру. У генерального директора может быть как один непосредственный подчиненный, так и несколько или ни одного. На рисунке отдел продаж находится левее отдела маркетинга, но порядок на самом деле не имеет значения. Единственное ограничение дерева — каждый узел может иметь не более одного родителя. Самый верхний узел (совет директоров, в нашем случае) родителя не имеет. Этот узел называется «корневым», или «корнем».
Двоичное дерево поиска
Двоичное дерево поиска похоже на дерево из примера выше, но строится по определенным правилам:
- У каждого узла не более двух детей.
- Любое значение меньше значения узла становится левым ребенком или ребенком левого ребенка.
- Любое значение больше или равное значению узла становится правым ребенком или ребенком правого ребенка.
Давайте посмотрим на дерево, построенное по этим правилам:
Двоичное дерево поиска
Обратите внимание, как указанные ограничения влияют на структуру дерева. Каждое значение слева от корня (8) меньше восьми, каждое значение справа — больше либо равно корню. Это правило применимо к любому узлу дерева.
Учитывая это, давайте представим, как можно построить такое дерево. Поскольку вначале дерево было пустым, первое добавленное значение — восьмерка — стало его корнем.
Мы не знаем точно, в каком порядке добавлялись остальные значения, но можем представить один из возможных путей. Узлы добавляются методом Add, который принимает добавляемое значение.
1 2 3 4 5 6 7 8 | 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 очень простой:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | 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.
Кроме того, в классе есть ссылка на корневой узел дерева и поле с общим количеством узлов.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | 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) в худшем случае.
Добавление узла не представляет особой сложности. Оно становится еще проще, если решать эту задачу рекурсивно. Есть всего два случая, которые надо учесть:
- Дерево пустое.
- Дерево не пустое.
Если дерево пустое, мы просто создаем новый узел и добавляем его в дерево. Во втором случае мы сравниваем переданное значение со значением в узле, начиная от корня. Если добавляемое значение меньше значения рассматриваемого узла, повторяем ту же процедуру для левого поддерева. В противном случае — для правого.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | 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) возвращает найденный узел и его родителя, поскольку мы должны заменить левого или правого ребенка родителя удаляемого узла.
Мы, конечно, можем избежать этого, если будем хранить ссылку на родителя в каждом узле, но это увеличит расход памяти и сложность всех алгоритмов, несмотря на то, что ссылка на родительский узел используется только в одном.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | 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.
1 2 3 4 5 6 7 | public int Count { get { return _count; } } |
Метод Clear
- Поведение: Удаляет все узлы дерева.
- Сложность: O(1)
1 2 3 4 5 | public void Clear() { _head = null; _count = 0; } |
Обход деревьев
Обходы дерева — это семейство алгоритмов, которые позволяют обработать каждый узел в определенном порядке. Для всех алгоритмов обхода ниже в качестве примера будет использоваться следующее дерево:
Пример дерева для обхода
Методы обхода в примерах будут принимать параметр Action<T>, который определяет действие, поизводимое над каждым узлом.
Также, кроме описания поведения и алгоритмической сложности метода будет указываться порядок значений, полученный при обходе.
Метод Preorder (или префиксный обход)
- Поведение: Обходит дерево в префиксном порядке, выполняя указанное действие над каждым узлом.
- Сложность: O(n)
- Порядок обхода: 4, 2, 1, 3, 5, 7, 6, 8
При префиксном обходе алгоритм получает значение текущего узла перед тем, как перейти сначала в левое поддерево, а затем в правое. Начиная от корня, сначала мы получим значение 4. Затем таким же образом обходятся левый ребенок и его дети, затем правый ребенок и все его дети.
Префиксный обход обычно применяется для копирования дерева с сохранением его структуры.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 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
При постфиксном обходе мы посещаем левое поддерево, правое поддерево, а потом, после обхода всех детей, переходим к самому узлу.
Постфиксный обход часто используется для полного удаления дерева, так как в некоторых языках программирования необходимо убирать из памяти все узлы явно, или для удаления поддерева. Поскольку корень в данном случае обрабатывается последним, мы, таким образом, уменьшаем работу, необходимую для удаления узлов.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 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
Инфиксный обход используется тогда, когда нам надо обойти дерево в порядке, соответствующем значениям узлов. В примере выше в дереве находятся числовые значения, поэтому мы обходим их от самого маленького до самого большого. То есть от левых поддеревьев к правым через корень.
В примере ниже показаны два способа инфиксного обхода. Первый — рекурсивный. Он выполняет указанное действие с каждым узлом. Второй использует стек и возвращает итератор для непосредственного перебора.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | 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).
1 2 3 4 5 6 7 8 9 | public IEnumerator GetEnumerator() { return InOrderTraversal(); } System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); } |
Продолжение следует
На этом мы заканчивает пятую часть руководства по алгоритмам и структурам данных. В следующей статье мы рассмотрим множества (Set).
Перевод статьи «The Binary Search Tree»