Работа с бинарным деревом поиска

Бинарное дерево поиска является нелинейной структурой для хранения множества элементов. Как и любая списковая структура, дерево должно допускать вставку, удаление и поиск элементов. Для поискового дерева требуется такая операция вставки, которая правильно располагает новый элемент. Рассмотрим, например, вставку узла 8 в дерево BinSTree_1. Начав с корневого узла 25, определяем, что узел 8 должен быть в левом поддереве узла 25 (8<25). В узле 10 определяем, что место узла 8 должно быть в левом поддереве узла 10, которое в данный момент пусто. Узел 8 вставляется в дерево в качестве левого сына узла 10.

До каждого вставляемого в дерево узла существует конкретный путь. Тот же путь может использоваться для поиска элемента. Поисковый алгоритм берет ключ и ищет его в левом или в правом поддереве каждого узла, составляющего путь. Например, поиск элемента 30 на дереве BinSTree_1 (Рис. 10) начинается в корневом узле 25 и переходит в правое поддерево (30 > 25), а затем в левое поддерево. (30 < 37). Поиск прекращается на третьем сравнении, когда ключ совпадает с числом 30, хранящемся в узле.

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

На первый взгляд напрашивается решение выбрать сына узла 25 — скажем, 37 — и заменить его родителя. Однако это простое решение терпит неудачу, так как некоторые узлы оказываются не с той стороны корня. Поскольку данное дерево относительно невелико, мы можем установить, что 15 или 30 являются допустимой заменой корневому узлу.