Программная реализация бинарных поисковых деревьев
В этой статье мы рассмотрим особенности реализации основных операций с бинарными поисковыми деревьями в исходном коде.
Рекомендуется вначале ознакомиться с теорией и описаниями алгоритмов в псевдокоде (см. Файл:Book iRunner BinTree.pdf).
В статье будут приводиться примеры работы с деревьями на трёх языках программирования: Java, C++ и Python.
Реализация тех же деревьев на языке C# похожа на Java-реализацию и обладает сопоставимой производительностью. Для простоты код на языке C# в этой статье не приводится.
Язык C++ сильно отличается от остальных. Используется другой синтаксис (указатели вместо ссылок), применяется ручное управление памятью (освобождение памяти при удалении вершин), больше мест, где можно совершить трудноуловимую ошибку. Однако на практике программы на C++ обычно работают быстрее всего.
Код на Python можно рассматривать как псевдокод: он обычно прост и понятен даже тем, кто с языком не сталкивался. В силу динамической природы языка программы на Python обычно работают сильно медленнее даже по сравнению с Java, но часто выглядят лаконичнее и пишутся быстрее.
Java
Класс вершины дерева
Самый простой класс вершины дерева при реализации на Java имеет следующий вид.
private class Node { public int key; public Node left; public Node right; public Node(int key) { this.key = key; } }
Конструктор объекта Node принимает один параметр — ключ, который будет иметь вершина (по построению бинарного поискового дерева, у каждой вершины есть ключ, вершина без ключа не существует, поэтому нет смысла делать конструктор вершины без параметра). Ссылки на левое и правое поддерево по умолчанию остаются нулевыми (null).
Класс дерева
class Tree { private Node root; }
При размещении класса вершины внутри класса дерева его объявляют статическим:
class Tree { static class Node { int key; Node left; Node right; } private Node root; }
Добавление ключа в дерево
Рекурсивная реализация
Приведём реализацию метода insert() и вспомогательной функции doInsert() класса Tree.
public void insert(int x) { root = doInsert(root, x); } private static Node doInsert(Node node, int x) { if (node == null) { return new Node(x); } if (x < node.key) { node.left = doInsert(node.left, x); } else if (x > node.key) { node.right = doInsert(node.right, x); } return node; }
Нерекурсивная реализация
Приведём возможную реализацию метода insert() класса Tree на языке Java.
Мы спускаемся по дереву, начиная от корня, в поисках места для вставки. Переменная node ссылается на текущую вершину, parent на её предка. Если вставляемый ключ меньше текущего, идём влево; если больше, то идём вправо; если равен, то останавливаемся и выходим: ключ уже есть в дереве и вставлять не нужно. Когда переменная node примет нулевое значение, место для вставки найдено. Создаём новую вершину и в предке parent исправляем ссылку left или right в зависимости от того, влево или вправо мы пошли из parent. Отдельный случай — когда дерево изначально было пусто, тогда нужно обновить поле root в объекте дерева (создан новый корень).
public void insert(int x) { Node parent = null; Node node = root; while (node != null) { parent = node; if (x < node.key) { node = node.left; } else if (x > node.key) { node = node.right; } else { return; } } Node newNode = new Node(x); if (parent == null) { root = newNode; } else if (x < parent.key) { parent.left = newNode; } else if (x > parent.key) { parent.right = newNode; } }
Можно написать то же немного по-другому: не поддерживать ссылку на вершину-предка при спуске, а смотреть на шаг вперёд и сразу заменять ссылки left или right у текущей вершины, если они нулевые.
public void insert(int x) { if (root == null) { root = new Node(x); return; } Node node = root; while (true) { if (x < node.key) { if (node.left == null) { node.left = new Node(x); return; } else { node = node.left; } } else if (x > node.key) { if (node.right == null) { node.right = new Node(x); return; } else { node = node.right; } } else { return; } } }
Сложно отдать предпочтение той или иной реализации.
C++
Класс вершины дерева
Приведём простейший пример класса вершины для языка C++.
class TNode { public: TNode(int key) : Key(key) , Left(0) , Right(0) { } int Key; TNode* Left; TNode* Right; };
В языке программирования C++ для связывания вершин обычно используют указатели. Ссылки языка C++ (называемые по-английски references и обозначаемые через TNode&) не подходят для этой цели, потому что не могут быть нулевыми и не допускают переназначения с одного объекта на другой (ссылка пожизненно указывает на один и тот же адрес).
Хорошим стилем при программировании на C++ является использование в конструкторах списков инициализации для полей класса, как показано выше, вместо присваивания полям значений в теле конструктора. Такой вариант допустим, но не рекомендуется:
class TNode { public: TNode(int key) { Key = key; Left = 0; Right = 0; } int Key; TNode* Left; TNode* Right; };
Важно, что поля указателей на левого и правого сына нужно обнулять явно (в Java это делается автоматически). Чтение полей класса, которые относятся к простым типам (целые числа, логические переменные, указатели и пр.) и не были инициализированы явно, приводит к неопределённому поведению. Такие ошибки может быть довольно трудно найти.
В новом стандарте C++11 можно инициализировать поля в месте объявления. Для нулевых указателей рекомендуется использовать константу nullptr вместо NULL или 0 для большей выразительности.
class TNode { public: TNode(int key) : Key(key) { } int Key; TNode* Left = nullptr; TNode* Right = nullptr; };
Этот код компилируется в Visual Studio 2013 и в g++ 4.7.2 с включенной опцией --std=c++11. К сожалению, в Visual Studio 2010 и более ранних версиях такой вариант не компилируется: инициализация полей по стандарту C++03 возможна только в конструкторе.
Класс дерева
В языке C++ логично класс дерева также оснастить деструктором, чтобы при уничтожении дерева удалялись все его вершины. Освобождение памяти выполняется рекурсивно посредством обратного обхода дерева.
class TTree { public: TTree() : Root(0) { } ~TTree() { DestroyNode(Root); } private: static void DestroyNode(TNode* node) { if (node) { DestroyNode(node->Left); DestroyNode(node->Right); delete node; } } private: TNode* Root; };
Добавление ключа в дерево
Нерекурсивная реализация
На языке C++ реализация нерекурсивного добавления ключа получается проще за счёт того, что в языке поддерживается создание указателей на указатели, в то время как в Java ничего подобного нет. В приведённой ниже реализации переменная cur имеет именно такой тип с двумя звёздочками. Получается, что величина *cur представляет собой указатель на текущую вершину node, хранящийся в вершине-предке (или в поле Root класса дерева для корня, у которого нет предка), и мы можем этот указатель изменять, создавая новую вершину, посредством указателя на указатель.
void TTree::Insert(int x) { TNode** cur = &Root; while (*cur) { TNode& node = **cur; if (x < node.Key) { cur = &node.Left; } else if (x > node.Key) { cur = &node.Right; } else { return; } } *cur = new TNode(x); }
Python
Класс вершины дерева
Приведём простой пример класса вершины дерева при реализации на Python.
class Node(object): def __init__(self, key): self.key = key self.left = None self.right = None
Функция-конструктор устанавливает в поле key заданный ключ, а также создаёт ссылки на левое и правое поддерево с именами left и right, по умолчанию нулевые (None).
Класс дерева
class Tree(object): def __init__(self): self.root = None
Поиск ключа в дереве
Рекурсивная реализация
Создаётся функция, которая принимает на вход корень некоторого поддерева (возможно, этот корень нулевой, то есть поддерева не существует) и ключ, который нужно найти. Функция возвращает ссылку на найденную вершину или None, если ключа нет.
def search_recursively(v, x): if v is None or v.key == x: return v elif x < v.key: return search_recursively(v.left, x) else: # x > v.key return search_recursively(v.right, x)
При первом вызове указанной функции следует передавать ей в качестве вершины v корень дерева:
search_recursively(tree.root, x)
Нерекурсивная реализация
Тот же алгоритм может быть реализован нерекурсивно при помощи цикла.
def search_iteratively(x): v = root while v is not None: if v.key == x: return v elif x < v.key: v = v.left else: # x > v.key: v = v.right return None
Добавление ключа в дерево
Рекурсивная реализация
Используя рекурсию, операцию вставки часто реализуют так. Создаётся функция, параметрами которой являются корень поддерева (возможно None) и ключ, который нужно добавить. Функция осуществляет вставку ключа в поддерево и возвращает корень поддерева после вставки (корень мог поменяться в единственном случае: поддерево изначально не существовало и была создана новая вершина, которая становится корнем; иначе функция просто возвращает тот же корень, который был ей передан).
def insert_recursively(v, x): if v is None: return Node(x) if x < v.key: v.left = insert_recursively(v.left, x) elif x > node.key: v.right = insert_recursively(v.right, x) # v.key == x return v
Вызывать такую функцию нужно из корня дерева и при этом присваивать корню возвращаемое значение, чтобы был обработан случай изначально пустого дерева:
tree.root = insert_recursively(tree.root, x)
Нерекурсивная реализация
Если не использовать рекурсию, то код получается более сложным.
Мы спускаемся посредством цикла по дереву, начиная от корня, в поисках места для вставки. Чтобы, найдя пустое место, иметь возможность заменить его на новую вершину, в коде кроме ссылки на текущую вершину v мы поддерживаем ссылку на вершину-предка в переменной parent. Если вставляемый ключ меньше текущего, идём влево; если больше, то идём вправо; если равен, то останавливаемся и выходим: ключ уже есть в дереве и вставлять не нужно. Когда переменная v примет нулевое значение None, место для вставки найдено. Создаём новую вершину и в предке parent исправляем ссылку left или right в зависимости от того, влево или вправо мы двигались из parent до того, как попали в None. Отдельный случай — когда дерево изначально было пусто, тогда нужно обновить переменную root (создан новый корень).
def insert_iteratively(x): parent = None v = tree.root while v is not None: parent = v if x < v.key: v = v.left elif x > v.key: v = v.right else: # x == v.key return w = Node(x) if parent is None: tree.root = w elif x < parent.key: parent.left = w elif x > parent.key: parent.right = w
Удаление из дерева
Рекурсивная реализация
При помощи рекурсии удаление из дерева вершины с заданным ключом обычно осуществляется так. Реализуется функция (будем называть её delete_recursively()), которая принимает на вход вершину v и ключ x. Функция выполняет удаление вершины с ключом x в поддереве с корнем v, если такой ключ там есть. Функция возвращает новый корень поддерева после удаления (корень v может поменяться, если он сам окажется удалён).
Функцию нужно вызывать из корня дерева и при этом присваивать корню возвращаемое значение:
tree.root = delete_recursively(tree.root, x)
В коде функции вначале делаются проверки ключа и выполняется спуск по дереву в поисках x (если меньше — идём влево, если больше — идём вправо). Когда функция delete_recursively() оказывается вызванной для вершины v с ключом x, мы переходим непосредственно к удалению. Сначала проверяется число потомков вершины v. Если левое и/или правое поддерево отсутствует, это простой случай. Иначе, когда есть оба поддерева, действия отличаются в зависимости от того, выполняется удаление левое или правое. Рассмотрим случай правого удаления. Вызывается вспомогательная функция find_min(), которая ищет вершину с наименьшим ключом min_key в правом поддереве вершины v. Затем ключ в вершине v заменяется на найденный наименьший ключ min_key, а исходная вершина с ключом min_key удаляется через новый вызов функции delete_recursively().
def delete_recursively(v, x): if v is None: return None if x < v.key: v.left = delete_recursively(v.left, x) return v elif x > v.key: v.right = delete_recursively(v.right, x) return v # v.key == x if v.left is None: return v.right elif v.right is None: return v.left else: # both subtrees are present min_key = find_min(v.right).key v.key = min_key v.right = delete_recursively(v.right, min_key) return v
Вспомогательная функция find_min() находит вершину с наименьшим ключом в поддереве с корнем v. Выполняется рекурсивный спуск по дереву всё время влево (там ключи меньше):
def find_min(v): if v.left is not None: return find_min(v.left) else: return v
Нерекурсивная реализация
Реализация удаления вершины с заданным ключом без использования рекурсии получается немного сложнее.
Для начала определим вспомогательную функцию, которая у вершины parent заменит вершину-сына old на вершину new (если в качестве parent будет передано значение None, то заменён будет корень всего дерева):
def replace_child(parent, old, new): if parent is None: tree.root = new elif parent.left == old: parent.left = new elif parent.right == old: parent.right = new
Для поиска вершины с ключом x можно было бы воспользоваться ранее разработанной функцией поиска, но она потребовала бы доработки: для удаления нужно знать не только ссылку на саму вершину v с ключом x, но и ссылку на её предка parent. Поэтому для понятности мы реализуем поиск ещё раз.
В целом, логика удаления здесь та же, как и в рекурсивной реализации. Когда мы ищем вершину с наименьшим ключом в правом поддереве, мы также вынуждены поддерживать при спуске ссылку на предка, чтобы потом иметь возможность эту вершину удобно удалить (вершина min_node_parent является предком вершины min_node).
def delete_iteratively(x): parent = None v = tree.root while True: if v is None: return if x < v.key: parent = v v = v.left elif x > v.key: parent = v v = v.right else: # x == v.key break result = None if v.left is None: result = v.right elif v.right is None: result = v.left else: min_node_parent = v min_node = v.right while min_node.left is not None: min_node_parent = min_node min_node = min_node.left result = v v.key = min_node.key replace_child(min_node_parent, min_node, min_node.right) replace_child(parent, v, result)
Основные алгоритмические ошибки
Многократное перевычисление одинаковых значений
Допустим, ставится задача: пометить все вершины дерева, у которых высоты левого и правого поддеревьев равны, при этом высота отсутствующего поддерева полагается равной −1.
Студент пишет код на Java (на других языках всё аналогично) следующего вида: в вершинах есть логическая переменная flag, есть рекурсивная функция mark(), которая прямым обходом расставляет эти флаги, используя при этом другую функцию getHeight(). Эта функция рекурсивно считает высоту вершины дерева по определению. Заметим, что функция сделана статической, а не методом класса, чтобы её можно было смело вызывать от нулевых вершин (getHeight(null)).
class Node { Node left; Node right; boolean flag; void mark() { if (getHeight(left) == getHeight(right)) { flag = true; } if (left != null) { left.mark(); } if (right != null) { right.mark(); } } static int getHeight(Node node) { int height = -1; if (node != null) { return Math.max(getHeight(node.left), getHeight(node.right)) + 1; } else { return -1; } } }
Код выглядит компактно, но работает медленно. Писать так не следует.
Проблема в том, что getHeight() для одной и той же вершины оказывается вызвана много раз. Происходит многократный пересчёт одних и тех же высот.
Чтобы было понятнее, рассмотрим пример.
Когда mark() будет выполняться для корня дерева 8, рекурсивно вызовется getHeight() от вершин 3, 1, 6, 4, 7, 10, 14, 13. Затем, когда mark() будет обрабатывать вершину 3, вызовется getHeight() от вершин 1, 6, 4, 7. И так далее. Для дерева большого размера время, которое уходит впустую, может быть значительным. Худший случай для такого алгоритма — дерево-цепочка из [math]N[/math] вершин (весь код по маркировке вершин выполнит порядка [math]N^2[/math] операций, а нужно решить задачу за линейное время).
Способов исправить ситуацию несколько:
- можно запоминать уже вычисленные высоты в полях вершин (высоты можно будет вычислить отдельным обходом или вычислять их динамически, но только те, что ещё не посчитаны);
- можно совместить работу функций
mark()иgetHeight(): считать высоты и расставлять флаги одним обходом.
Левое и правое удаление
Подчеркнём ещё раз. «Левое» и «правое» удаления отличаются лишь в случае, когда удаляемая вершина имеет оба поддерева. Если у вершины одно поддерево или вершина является листом, удаление выполняется единственным способом.
Рассмотрим пример. Пусть исходное дерево построено по ключам 1, 3, 2, 4. Требуется выполнить «правое» удаление вершины с ключом 1. В данном случае у удаляемой вершины нет левого поддерева, поэтому нет такого понятия, как «правое» («левое») удаление, т. е. не нужно искать в правом (левом) поддереве минимальный (максимальный) ключ и заменять им удаляемый. Правильный подход: вершина 1 непосредственно сама удаляется, а её правое поддерево остается без перестройки.
Для наглядности приведём рисунки. На первом рисунке показано исходное дерево. На втором рисунке изображено дерево, которое получается после удаления вершины 1 (не важно, «левого» или «правого» удаления, результат одинаковый). На третьем рисунке показан неправильный результат.
Основные ошибки в реализации
Copy-Paste
Нередко в решениях студентов можно увидеть большое число однотипного кода, полученного путём копирования и вставки. Это плохая практика. Часто ошибки появляются в разборе случаев. Однако общие рекомендации по написанию кода здесь дать сложно, всё сильно зависит от конкретной задачи.
Например, для вычисления высоты дерева часто пишется такой код:
class Node { Node left; Node right; int height; void calcHeight() { if (left != null) { left.calcHeight(); } if (right != null) { right.calcHeight(); } if (left != null && right != null) { if (left.height > right.height) { height = left.height + 1; } else { height = right.height + 1; } } else if (left != null) { height = left.height + 1; } else if (right != null) { height = right.height + 1; } else { height = 0; } } }
Тот же код можно переписать короче:
class Node { Node left; Node right; int height; void calcHeight() { height = 0; if (left != null) { left.calcHeight(); height = Math.max(height, left.height + 1); } if (right != null) { right.calcHeight(); height = Math.max(height, right.height + 1); } } }
Или ещё короче:
class Node { Node left; Node right; int height; static int calcHeight(Node node) { if (node != null) { return node.height = Math.max(calcHeight(node.left), calcHeight(node.right)) + 1; } else { return -1; } } }
Нулевые ссылки
Нередко студенты забывают проверять ссылку на вершину на равенство нулю перед тем, как обращаться по этой ссылке (в тех местах, где ссылка действительно бывает нулевой).
if (x < node.key && node != null) { // бабах!
В языке Java обращение по нулевой ссылке приводит к выбрасыванию исключения NullPointerException. По умолчанию такое исключение не обрабатывается и приводит к завершению программы с ошибкой во время выполнения. Если на каком-то уровне в программе сознательно отлавливаются все исключения, программа может завершаться с нулевым кодом выхода (будто бы корректно), но при этом работать неправильно: выводить неправильный ответ или не выводить ответ совсем.
В языке C# всё аналогично Java, только исключение называется NullReferenceException.
В языке C++ разыменование нулевого указателя является неопределённым поведением и на практике часто приводит к мгновенному краху программы.
Инициализация полей класса
Проблема специфична для языка С++. Часто студенты добавляют поля в свой класс вершины дерева, но забывают проинициализировать их (возможно, при некоторых условиях) и там остаётся «мусор». Чтение неинициализированных данных является неопределённым поведением.
class TNode { public: TNode(int key) : Key(key) , Left(nullptr) , Right(nullptr) { } int Key; int Depth; // забыли проинициализировать в конструкторе TNode* Left; TNode* Right; };
Рекурсия и системный стек
Когда дерево обрабатывается рекурсивным алгоритмом, система сохраняет локальные переменные, адрес возврата и, возможно, некоторую дополнительную информацию для каждого выполняемого экземпляра рекурсивной функции в специальной области памяти, которая называется системным стеком, чтобы можно было продолжить выполнение функции при возврате из очередного рекурсивного вызова. Получается, рекурсивные программы в пике (когда обрабатываются самые глубокие листья) используют объём стековой памяти, пропорциональный высоте дерева.
Следует понимать, что в общем случае бинарное поисковое дерево не является сбалансированным и может иметь большую высоту. В сбалансированном дереве высота имеет величину порядка двоичного логарифма от общего числа вершин в дереве. Для несбалансированного дерева эта оценка неверна, и высота может расти линейно с ростом числа вершин.
Так, на рисунках показаны два дерева из семи вершин. Первое дерево имеет высоту 2, а второе — высоту 6.
При обработке деревьев большой высоты часто размера системного стека оказывается недостаточно, и происходит переполнение стека. В качестве решения этой проблемы можно увеличить размер стека, как рекомендуется в инструкции.
Освобождение памяти
В языке C++ нет сборщика мусора, и нужно самостоятельно освобождать всю выделенную память. Необходимо вызывать оператор delete для каждого объекта, созданного при помощи new.
Часто студенты забывают освобождать память при удалении вершины дерева. Например:
node->Left = node->Left->Right; // память под вершину node->Left утекла, ссылок на неё больше нет
Правильно делать так:
TNode* nodeToDelete = node->Left; node->Left = node->Left->Right; delete nodeToDelete;
Ещё чаще забывают корректно уничтожить все вершины дерева перед выходом из программы.
int main() { TNode* node = new Node(42); // ... // забыт delete node; return 0; }
Тестирующая система прощает эти недоработки. Неосвобождённая память не приводит к ошибкам во время выполнения. Решения запускаются заново для каждого теста, а по завершении работы решения на тесте операционная система в любом случае освободит всю память. Тем не менее, в промышленной разработке программного обеспечения на C/C++ любые утечки памяти недопустимы.
В языках C#, Java, Python явно освобождать память вручную не нужно.
