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

Задача

Реализовать структуру «Двоичное дерево поиска» в соответствии с этим шаблоном.

Решение

По моему субъективному мнению, тут следует привести более ли менее детальное описание только операций вставки и удаления вершины.

Операция вставки

Пусть у нас есть вершина с ключом [latex]key[/latex] и дерево [latex]T[/latex], в которое нам нужно вставить нашу вершину. Сразу у нас есть ссылка только на корень дерева, поэтому посмотрим на значение ключа в корне дерева. Если оно вдруг совпало с нашим [latex]key[/latex], то, в этой реализации, мы заменяем поля этой вершины на новые. Если оно не совпало, то так как нам нужно найти незанятое место, куда бы мы могли вставить нашу вершину, мы проверяем: если значение нашего [latex]key[/latex] больше значения в корне — правое поддерево [latex]T[/latex], иначе — левое. Можно заметить, что ситуация изменилась только значением ключа в корне, поэтому можно применить наши прошлые действия. Так мы будем делать, пока наш выбор не остановится на пустом поддереве, то есть — пока не найдется места для нашей вершины. Теперь, когда мы нашли приют нашей вершине, мы вставляем ее на это место.

Операция удаления

Для того, чтобы удалить вершину, нам, очевидно, нужно ее сначала найти, при этом, у нас есть только ключ этой вершины. И да, мы будем не одни, с нами пойдет указатель на предыдущую вершину в дереве. Искать мы будем способом, описанным в предыдущем пункте. Если значение нашего ключа и ключа в корне совпало — мы нашли обреченную вершину, если же мы попали в пустое поддерево — можно считать, что наша работа выполнена (нет вершины — нет проблемы). Однако рассмотрим первый случай.
Пусть правое (левое) поддерево пусто. Тогда удалить вершину просто — мы заменяем адрес удаляемой вершины у предыдущей вершины (там ведь стоит указатель) на адрес левого (правого) поддерева удаляемой вершины.
Если же правое поддерево не пусто, мы уже не можем просто удалить вершину. Чтобы сохранить основное свойство дерева мы должны найти замену. В правом поддереве мы найдем вершину с наименьшим ключом и поменяем с удаляемой вершиной (если есть еще какие-то поля — их тоже заменяем). Задача свелась к первому случаю.

Код

4 thoughts on “Двоичное дерево поиска

  1. Необходимо:
    1) постановка задачи,
    2) тестовый вывод,
    3) пояснения (можно и кратко),
    4) ссылка на online IDE.

  2. Это результат c 10000 итераций. Адеоне просто не может это вывести, а нетбинкс может.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *