Реферат: Двоичные деревья поиска
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 К-во Просмотров: 881
Бесплатно скачать Реферат: Двоичные деревья поиска
|