Claw.ru | Рефераты по информатике, программированию | Двоичные деревья поиска Двоичные деревья поиска | Категория реферата: Рефераты по информатике, программированию | Теги реферата: отчет о прохождении практики, шпоры на экзамен | Добавил(а) на сайт: Dvoreckov. Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата     // меньше ключа текущей вершины     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, если потомков нет). Далее вершина удаляется из дерева, при этом отдельно рассматриваются случаи: когда потомков нет и когда удаляемая вершина – это корень дерева. Возвращаемое значение – это указатель на удалённую вершину. На неё уже нет никаких ссылок в самом дереве, но она всё ещё занимает память. Момент её реального удаления зависит от используемых методов распределения памяти.