NIL, NULL и маленькие хитрости

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

Роман Акопов 

Определение Двоичного Дерева Поиска (Binary Search Tree, BST)

Двоичным деревом поиска (ДДП) называют дерево, все вершины которого упорядочены, каждая вершина имеет не более двух потомков (назовём их левым и правым), и все вершины, кроме корня, имеют родителя. Вершины, не имеющие потомков, называются листами. Подразумевается, что каждой вершине соответствует элемент или несколько элементов, имеющие некие ключевые значения, в дальнейшем именуемые просто ключами. Обычно одной вершине соответствует один элемент, поэтому данные термины можно без потери смысла считать синонимами, хотя и надо помнить, что в некоторых реализациях это не так. В приведённых алгоритмах считается, что одной вершине соответствует только один элемент. Поэтому мы будем использовать понятия ключа вершины и данных вершины, подразумевая ключ и данные соответствующего вершине элемента. Мы так же будем понимать под вставкой вершины добавление вершины с указанным значением элемента и присвоение указателям на родителя и потомков корректных значений. Именно ключ используется во всех операциях сравнения элементов. Элемент может также содержать ассоциированные с ключом данные. На практике в качестве ключа может использоваться часть данных элемента. Ключ также может храниться как отдельное значение. ДДП позволяет выполнять следующие основные операции:

Поиск вершины по ключу.

Определение вершин с минимальным и максимальным значением ключа.

Переход к предыдущей или последующей вершине, в порядке, определяемом ключами.

Вставка вершины.

Удаление вершины.

Двоичное дерево может быть логически разбито на уровни. Корень дерева является нулевым уровнем, потомки корня – первым уровнем, их потомки – вторым, и т.д. Глубина дерева это его максимальный уровень. Понятие глубины также может быть описано в терминах пути, то есть глубина дерева есть длина самого длинного пути от корня до листа, если следовать от родительской вершины до потомка. Каждую вершину дерева можно рассматривать как корень поддерева, которое определяется данной вершиной и всеми потомками этой вершины, как прямыми, так и косвенными. Поэтому о дереве можно говорить как о рекурсивной структуре. Эффективность поиска по дереву напрямую связана с его сбалансированностью, то есть с максимальной разницей между глубиной левого и правого поддерева среди всех вершин. Имеется два крайних случая – сбалансированное бинарное дерево (где каждый уровень имеет полный набор вершин) и вырожденное дерево, где на каждый уровень приходится по одной вершине. Вырожденное дерево эквивалентно связанному списку. Время выполнения всех основных операций пропорционально глубине дерева. Таким образом, скоростные характеристики поиска в ДДП могут варьироваться от O(log2N) в случае законченного дерева до O(N) – в случае вырожденного.

ДДП может быть использовано для реализации таких абстракций, как сортированный список, словарь (набор соответствий "ключ-значение"), очередь с приоритетами и так далее.

При реализации дерева помимо значения ключа (key) и данных также хранятся три указателя: на родителя (net), левого (left) и правого (right) потомков. Если родителя или потомка нет, то указатель хранит нулевое (NULL, NIL) значение.

Свойство упорядоченности двоичного дерева поиска

Если x – это произвольная вершина в ДДП, а вершина y находится в левом поддереве вершины x, то y.key <= x.key. Если x – это произвольная вершина ДДП, а вершина y находится в правом поддереве вершины x, то y.key >= x.key. Из свойства следует, что если y.key == x.key, то вершина y может находиться как в левом, так и в правом поддереве относительно вершины x.

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

Это двоичное дерево поиска:

 

Рисунок 1.

А это нет:

 

Рисунок 2.

Способы обхода ДДП

Есть три способа обхода: Прямой (preorder), Поперечный (inorder), Обратный (postorder).

Прямой обход: сначала обходится данная вершина, левое поддерево данной вершины, затем правое поддерево данной вершины.

Поперечный обход: сначала обходится левое поддерево данной вершины, затем данная вершина, затем правое поддерево данной вершины. Вершины при этом будут следовать в неубывающем (по ключам key) порядке.

Обратный обход: сначала обходится левое поддерево данной вершины, затем правое, затем данная вершина.

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

 

Рисунок 3.

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

Поиск вершины в ДДП

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

Рекурсивно:

TreeSearch(node, key) Begin // Если вершина равна NIL, то нечего в ней искать. Так же и возвращаем. // Это нужно для поиска по не существующим потомкам If (node == NIL) Then Return node; // Если нашли, то возвращаем указатель на найденную вершину. If (node.key == key) Then Return node; // Если ключ найденной вершины больше того, который мы ищем If (node.key > key) Then // То искать в левом поддереве Return TreeSearch(node.left, key); Else // Иначе в правом поддереве Return TreeSearch(node.right, key); End
ПРИМЕЧАНИЕ В прилагаемом исходном коде, написанном на паскале-подобном языке, все параметры передаются по значению. nodeParent, nodeTemp и node – это указатели на вершины, а Tree – само дерево, имеющее поле root, указатель на корень дерева.

Итеративно:

TreeSearch(node,key) Begin // Пока ещё есть вершины среди которых можно искать //(мы просматриваем не все, но несколько) и пока мы не нашли While (node!= NIL) and (node.key!= key) Do Begin // Если ключ найденногй вершины больше того который мы ищем If (node.key > key) Then node = node.left; // То искать в левом поддереве Else node = node.right; // А иначе в правом поддереве End Return node; // Возвратить найденное End

Поиск вершины с минимальным и максимальным значением ключа

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

TreeMinimum(node) Begin While (node.left!= NIL) Do // Пока есть левый потомок Node = node.left; // Перейти к нему Return node; End   TreeMaximum(node) Begin While (node.right!= NIL) Do // Пока есть правый потомок node = node.right; // Перейти к нему Return node; End

Нахождение следующей и предыдущей вершины в ДДП

Чтобы найти предыдущую и следующую вершину, надо снова вспомнить свойство упорядоченности. Рассмотрим это на примере функции TreeNext. Она учитывает два случая. Если правое поддерево не пусто, то вершина из правого поддерева с минимальным значением ключа и будет следующей. Если же правое поддерево пусто, тогда мы идём вверх, пока не найдём вершину, являющуюся левым потомком своего родителя. Этот родитель (если он есть) и будет следующей вершиной. Возвращаемое значение – это указатель на вершину с следующим (предыдущим) значеним ключа или NIL, если такой вершины нет.

TreeNext(node) Begin // Если правое поддерево не пусто, то возвратить // вершину с минимальным значением ключа из правого поддерева If (node.right!= NIL) Then Return TreeMinimum(node.right); nodeParent = node.nodeParent; // Перебирать родителей, пока не найдена вершина, // являющаяся левым потомком своего родителя // или пока не закончатся родители. While (nodeParent!= NIL) and (node == nodeParent.right) Do Begin node = nodeParent; nodeParent = nodeParent.nodeParent; End // Возвратить родителя вершины, являющегося левым потомком своего родителя Return nodeParent; End   TreePrevious(node) Begin If (node.left!= NIL) Then // Если левое поддерево не пусто, то возвратить // вершину из левого поддерева с максимальным значением ключа Return TreeMaximum(node.left); nodeParent = node.nodeParent; // Перебирать родителей, пока не найдём вершину, являющуюся // правым потомком своего родителя или пока не закончатся родители While (nodeParent!= NIL) and (node == nodeParent.left) Do Begin node = nodeParent; nodeParent = nodeParent.nodeParent; End  // Возвратить родителя вершины являющегося его правым потомком  Return nodeParent; End

Добавление вершины

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

TreeInsert(Tree,node) Begin nodeParent = NIL; nodeTemp = T.root; // Пока ещё есть вершины которые надо просмотреть, то // есть пока мы не добрались до “листочков” дерева While (nodeTemp!= NIL) Do Begin nodeParent = nodeTemp; // Если ключ вершины, которую мы хотим вставить, // меньше ключа текущей вершины If (node.key < nodeTemp.key) Then nodeTemp = nodeTemp.left; // То он должен быть в его левом поддереве Else nodeTemp = nodeTemp.right; // А иначе в правом End node.nodeParent = nodeParent; If (nodeParent == NIL) Then // Если в дереве ещё нет вершин Tree.root = node; // То добавить первую Else Begin // Если ключ вершины, которую мы хотим вставить, // меньше ключа вершины, потомком которой должна стать // вставляемая вершина If (node.key < nodeParent.key) Then nodeParent.left = node; // То добавить в дерево как левого потомка Else nodeParent.right = node; // Иначе добавить в дерево как правого потомка End End

Удаление вершины

Проблемы возникают и при удалении. Нам необходимо сохранить свойство упорядоченности ДДП. При удалении возможны три случая: у удаляемой вершины нет потомков, у удаляемой вершины есть один потомок и у удаляемой вершины два потомка. Если потомков нет, то вершину можно просто удалить. Если потомок один, то удаляемую вершину можно “вырезать”, указав её родителю в качестве потомка единственного имеющегося потомка удаляемой вершины. Если же потомков два, требуются дополнительные действия. Нужно найти следующую за удаляемой (по порядку ключей) вершину, скопировать её содержимое (ключ и данные) в удаляемую вершину (она теперь никуда не удаляется физически, хотя логически исчезает) и удалить найденную вершину (у неё не будет левого потомка). Сначала функция TreeDelete ищет вершину, которую надо удалить, затем переменной nodeTemp присваивается указатель на существующего потомка удаляемой вершины (или NIL, если потомков нет). Далее вершина удаляется из дерева, при этом отдельно рассматриваются случаи: когда потомков нет и когда удаляемая вершина – это корень дерева. Возвращаемое значение – это указатель на удалённую вершину. На неё уже нет никаких ссылок в самом дереве, но она всё ещё занимает память. Момент её реального удаления зависит от используемых методов распределения памяти.

TreeDelete(Tree,node) Begin // Если потомков не более одного (случаи 1 и 2) If (node.left == NIL) or (node.right == NIL) Then del = node; // физически удаляем текущую вершину Else del = TreeNext(node); // Иначе следующую If (del.left!= NIL) Then // Пытаемся найти хоть одного потомка nodeTemp = del.left; Else nodeTemp = del.right; // Если есть, родителем потомка делаем родителя // удаляемой вершины (случай 2) If (nodeTemp!= NIL) Then nodeTemp.nodeParent = del.nodeParent; // Если удаляем корень дерева, надо указать новый корень дерева If (del.nodeParent == NIL) Then Tree.root = nodeTemp; Else Begin // Указываем родителю удаляемой вершины качестве потомка // потомок удаляемой вершины If (del.nodeParent.left == del) Then del.nodeParent.left = nodeTemp; Else del.nodeParent.right = nodeTemp; End If (del!= node) Then // Если случай 3 Begin node.key = del.key; // Скопировать ключ { копирование дополнительных данных } End Return del; End

NIL, NULL и маленькие хитрости

Нередко алгоритмы, просто выглядящие на бумаге, становятся нагромождением сплошных конструкций if в реальной программе. Почему? Ответ очевиден: многие алгоритмы для работы с деревьями предполагают, что (NIL).parent == (NIL).left == (NIL).right == NIL. Вроде всё ясно и даже логично, но ведь во многих языках программирования NIL/NULL – это ноль. А обращение по нулевому адресу памяти чревато нехорошими вещами. Что же делать? Ведь мало того, что все эти if тормозят программу, в них легко запутаться! Решение просто: мы не будем использовать NIL! Действительно, алгоритмам совершенно всё равно, какое численное значение имеет NIL, главное, чтобы адрес любой реальной вершины в дереве не был ему равен. Поэтому вместо NIL мы будем использовать адрес переменной, проинициализированной особым образом. Я покажу это на языке С++, но думаю, этот пример можно будет перевести и на другие языки, хотя там, скорее всего, нет шаблонов, и придется пожертвовать типобезопасностью.

template <class CTree>class CTreeBase { protected: CTree * lpCParent; CTree * lpCLeft; CTree * lpCRight; public: CTreeBase(CTreeBase * lpCParentInit, CTreeBase * lpCLeftInit, CTreeBase * lpCRightInit) { lpCParent = (CTree *)lpCParentInit; lpCLeft = (CTree *)lpCLeftInit; lpCRight = (CTree *)lpCRightInit; } };   ///////////////////////////////////// class CTree: public CTreeBase<CTree> { private: int data; protected: static CTreeBase<CTree> treeNil; }; //////////////////////////////////////////////////////////// CTreeBase<CTree> CTree::treeNil(&treeNil, &treeNil, &treeNil);

Теперь везде в классе CTree можно использовать переменную treeNil. Преимущества очевидны. Потратив каких-то двенадцать (3 * sizeof(CTree *)) байт памяти, мы упростили разработку и ускорили выполнение программы.

12	Поделиться:

Воспользуйтесь поиском по сайту: