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

Основные понятия

Деревом (англ. tree) называется связный граф без циклов. На практике часто приходится иметь дело со специальными видами деревьев. Наиболее распространенным среди них являются корневые деревья.

Корневое дерево (или ориентированное дерево с корнем, англ. directed rooted tree) — это ориентированный граф, который удовлетворяет следующим условиям:

1. имеется в точности одна вершина, в которую не входит ни одна дуга и которая называется корнем;
2. в каждую вершину, кроме корня, входит ровно одна дуга;
3. из корня имеется путь к каждой вершине.

Если в корневом дереве существует путь из [math]v[/math] в [math]w[/math], то [math]v[/math] называют предком вершины [math]w[/math], а [math]w[/math] — потомком вершины [math]v[/math]. Стоит отметить, что любая вершина является своим собственным потомком. Если вершина не имеет других потомков, то её называют висячей вершиной (англ. pendant vertex) или листом (мн. листьями, англ. leaf / leaves). Вершины, отличные от корня и листьев, называют внутренними.

Если [math](v, w)[/math] — дуга корневого дерева, то [math]v[/math] называется отцом (также родителем или непосредственным предком) вершины [math]w[/math], а [math]w[/math] называется сыном (или непосредственным потомком) вершины [math]v[/math]. Подграф, порождённый всеми потомками вершины [math]v[/math] (включая вершину [math]v[/math]) корневого дерева [math]T[/math], называется поддеревом (англ. subtree) корневого дерева [math]T[/math] с корнем в вершине [math]v[/math].

Глубиной (англ. depth) вершины [math]v[/math] в корневом дереве называется длина (в дугах) единственного пути из корня в эту вершину.

Высотой (англ. height) вершины [math]v[/math] в корневом дереве называется длина (в дугах) наибольшего пути из вершины [math]v[/math] до одного из его потомков. Высота корневого дерева — высота корня.

Уровнем (англ. level) вершины [math]v[/math] называется разность высоты дерева и глубины вершины [math]v[/math].

Упорядоченное корневое дерево — это корневое дерево, у которого дуги, выходящие из каждой вершины, упорядочены (в дальнейшем будем считать, что они упорядочены слева направо).

Бинарное дерево (англ. binary tree) — это упорядоченное корневое дерево, у каждой вершины которого имеется не более двух сыновей. В бинарном дереве каждый сын произвольной вершины определяется как левый или правый. Поддерево (если оно существует), корнем которого является левый сын вершины [math]v[/math], называется левым поддеревом вершины [math]v[/math]. Аналогичным образом определяется правое поддерево для вершины [math]v[/math].

Представление в памяти

Существует несколько способов представления бинарных деревьев (предполагаем, что вершины дерева занумерованы целыми числами от 1 до n).

1. Представление в виде двух массивов — Left и Right:
   • если вершина j является левым (правым) сыном вершины i, то Left[i] = j (Right[i] = j);
   • если у вершины i нет левого (правого) сына, то Left[i] = 0 (Right[i] = 0).
2. Представление в виде списковой структуры, когда каждый элемент списка содержит помимо информационной части (ключ вершины, дополнительные метки и т. п.), ссылку на левого и правого ее сыновей и, возможно, ссылку на отца:

type tree_ptr = ^tree vertex;
tree_vertex = record 
    element: element_type;
    left: tree_ptr;
    right: tree_ptr;
end;

Бинарное дерево поиска

Бинарное поисковое дерево высоты 3 с 9 вершинами, корнем 8 и листьями 1, 4, 7 и 13, средней по значению среди вершин дерева является вершина 7

Предположим, что каждой вершине бинарного дерева соответствует некоторое ключевое значение (например целое число). Бинарное дерево называется деревом поиска (бинарным поисковым деревом), если для каждой вершины [math]v[/math] ключи всех вершин в левом поддереве вершины [math]v[/math] меньше ключа вершины [math]v[/math], а ключи всех вершин в правом поддереве — больше. В поисковом дереве нет двух вершин с одинаковыми ключевыми значениями, если не оговорено иное. Минимальный (максимальный) элемент бинарного поискового дерева соответствует ключевому значению самой левой (правой) вершины дерева.

Во многих задачах требуется найти среднюю по значению из вершин дерева. Средней по значению является та из вершин дерева, которой соответствует ключевое значение [math]x[/math], для которого число вершин дерева, имеющих ключевое значение строго меньшее [math]x[/math], равно числу вершин дерева, имеющих ключевые значения строго большие [math]x[/math]. Если число вершин в дереве чётно, то будем считать, что средней по значению вершины не существует. Если же дерево состоит из единственной вершины, то будем полагать, что эта вершина является средней по значению.

Пути и полупути

Путём (англ. path) в орграфе называется чередующаяся последовательность [math]v_0, (v_0, v_1), v_1, (v_1, v_2), v_2, \ldots, v_n[/math] вершин и дуг. При этом дуги в пути не могут повторяться. Первая и последняя вершины пути называются крайними, а все остальные — внутренними. Под длиной пути будем понимать число дуг в нём. Так, на приведённом рисунке последовательность [math]8, (8, 3), 3, (3, 6), 6[/math] является путём длины 2.

Определим центральную вершину некоторого пути как вершину [math]v[/math], для которой число вершин в этом пути до неё равно числу вершин в этом пути после неё (если число вершин в пути чётно, то будем говорить, что центральной вершины для заданного пути не существует). Так, на приведённом рисунке для пути [math]8, (8, 3), 3, (3, 6), 6[/math] центральной вершиной является вершина 3.

Определим среднюю вершину некоторого пути как вершину [math]v[/math], для которой в этом пути число вершин с меньшим, чем у вершины [math]v[/math], ключом равно числу вершин с большим, чем у вершины [math]v[/math], ключом (если число вершин в пути чётно, то будем говорить, что средней вершины для заданного пути не существует). Так, на приведённом рисунке для пути [math]8, (8, 3), 3, (3, 6), 6[/math] средней вершиной является вершина 6.

Для полупути (англ. semipath) снимается ограничение на направление дуг. Например, последовательность [math]3, (8, 3), 8, (8, 10), 10[/math] является полупутём длины 2, но не является путём. В полупути, как и в пути, дуги не могут повторяться.

Корнем полупути будем называть ту из вершин этого полупути, которая находится на наибольшей высоте (если выписать дуги полупути, то из коня этого полупути дуги только выходят). Центральная и средняя вершины полупути определяются аналогично, как и для пути. Для полупути [math]3, (8, 3), 8, (8, 10), 10[/math] вершина 8 является и центральной, и средней, и корнем этого полупути.

Наибольшим полупутём (англ. maximum semipath) в дереве будем называть полупуть наибольшей длины (не стоит путать наибольший полупуть с максимальным полупутём (англ. maximal semipath) — полупутём, который нельзя продолжить; наибольший полупуть всегда является максимальным, а вот обратное не всегда верно). Следует отметить, что наибольший полупуть в дереве не обязательно соединяет некоторые два листа этого дерева. Так, например, если у корня дерева только одно поддерево, то наибольший полупуть может соединять корень дерева и один из листьев. Заметим, что в дереве может быть несколько корней полупутей наибольшей длины, а через один и тот же корень может проходить несколько различных полупутей наибольшей длины. Так, в дереве, приведённом на рисунке, есть два наибольших полупути: один соединяет вершину 4 и вершину 13, другой — вершину 7 и вершину 13. Оба эти полупути имеют длину 6 и имеют общий корень — вершину 8.

Обходы дерева

Бинарное поисковое дерево. Прямой левый обход: 8, 3, 1, 6, 4, 7, 10, 14, 13; обратный левый обход: 1, 4, 7, 6, 3, 13, 14, 10, 8; внутренний левый обход: 1, 3, 4, 6, 7, 8, 10, 13, 14

Многие алгоритмы, работая с бинарными корневыми деревьями, посещают один раз в определенном порядке каждую вершину дерева. Cуществуют три наиболее распространенных способа обхода вершин бинарного дерева (предполагаем, что бинарное дерево задано списковой структурой): прямой, обратный и внутренний.

Прямой обход

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

Приведем процедуру прямого левого обхода.

procedure order1(v: tree_ptr);
begin 
    if v <> nil then
    begin
        solve(v);
        order1(v^.left);
        order1(v^.right);
    end;
end;

Обратный обход

Обратный порядок обхода (снизу вверх) заключается в том, что корень дерева посещается после его поддеревьев. Если сначала посещается левое (правое) поддерево корня, то обход называется обратным левым (правым) обходом.

Приведем процедуру обратного левого обхода.

procedure order2(v: tree_ptr);
begin
    if v <> nil then
    begin
        order2(v^.left);
        order2(v^.right);
        solve(v);
    end;
end;

Внутренний обход

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

Приведем процедуру левого внутреннего обхода.

procedure order3(v: tree_ptr);
begin 
    if v <> nil then
        begin
        order3(v^.left); 
        solve(v);
        order3(v^.right);
    end;
end;

Для решения многих задач, предложенных в системе InsightRunner, может потребоваться вычисление для каждой вершины v некоторых меток, например, высоты, глубины, количества вершин в дереве с корнем в вершине v и др. Для выполнения этих действий можно использовать соответствующие процедуры обхода вершин дерева, а вычисления нужных меток выполнять в процедуре solve(v).

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

В некоторых задачах требуется выполнить удаление заданной вершины v из дерева (предположим, что f — отец удаляемой вершины).

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

• если v — корень дерева, то корнем дерева станет вершина w (если у вершины v сыновей не было, то дерево перестанет существовать);
• если v — лист, то ссылка у вершины f, указывающая на вершину v, станет пустой;
• если v не лист и не корень дерева, то ссылка у f, указывающая на v, будет указывать на w.

Случай удаления вершины v, у которой два поддерева, можно свести к предыдущему. При этом непосредственного удаления вершины v из дерева не происходит, а ключ вершины v заменяется на значение минимального (максимального) ключа среди вершин правого (левого) поддерева вершины v — такое удаление называют правым (левым).

Рассмотрим более подробно правое удаление. Предположим, что минимальный ключ в правом поддереве вершины v имела вершина z. Запишем ключ вершины z в вершину v, что приведёт к тому, что в дереве появятся две вершины v и z с одинаковыми ключевыми значениями, а это недопустимо для бинарного поискового дерева.

Поэтому, удаляем вершину z из дерева. Это сделать проще, так как вершина z не имеет левого поддерева (возможно, является листом) и завершаем процедуру удаления.

При реализации удаления нужно учитывать, что все внешние итераторы (указатели) для исходной вершины z с ключом d должны по-прежнему оставаться актуальными, поскольку вершина с ключом d продолжает существовать. В этом отношении имеет смысл, структурно удаляя из дерева вершину z, «физически» удалять всё равно вершину v, позволяя вершине z занять её место в дереве.