Бинарные деревья
Определение
Бинарное (двоичное) дерево (binary tree) - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла.

Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само является бинарным деревом и, следовательно, каждый его узел в свою очередь является корнем дерева.
Узел дерева, не имеющий потомков, называется листом.
Бинарное дерево может представлять собой пустое множество.

Особенности функций для работы с деревом.
При работе с деревьями обычно используются рекурсивные алгоритмы. Использование рекурсивных функций менее эффективно, поскольку многократный вызов функции расходует системные ресурсы. Тем не менее, использование рекурсивных функций является оправданным, поскольку нерекурсивные функции для работы с деревьями гораздо сложнее и для написания, и для восприятия кода программы.

Применение
Организация данных с помощью бинарных деревьев часто позволяет значительно сократить время поиска нужного элемента. Поиск элемента в линейных структурах данных обычно осуществляется путем последовательного перебора всех элементов, присутствующих в данной структуре. Поиск по дереву не требует перебора всех элементов, поэтому занимает значительно меньше времени. Максимальное число шагов при поиске по дереву равно высоте данного дерева, т.е. количеству уровней в иерархической структуре дерева.

Важным частным случаем графа является дерево. Деревом называется орграф для которого :
1. Существует узел, в которой не входит не одной дуги. Этот узел называется корнем.
2. В каждую вершину, кроме корня, входит одна дуга.
С точки зрения представления в памяти важно различать два типа деревьев: бинарные и сильноветвящиеся.

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

Представление выражений с помощью деревьев
С помощью деревьев можно представлять произвольные арифметические выражения. Каждому листу в таком дереве соответствует операнд, а каждому родительскому узлу - операция. В общем случае дерево при этом может оказаться не бинарным.

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

Представление сильноветвящихся деревьев
В ряде задач используются сильноветвящиеся деревья. Каждый элемент для представления бинарного дерева должен содержать как минимум три поля: значение или имя узла, указатель левого поддерева, указатель правого поддерева. Произвольные деревья могут быть бинарными или сильноветвящимися. Причем число потомков различных узлов не ограничено и заранее не известно.

Тем не менее, для представления таких деревьев достаточно иметь элементы, аналогичные элементам списковой структуры бинарного дерева. Элемент такой структуры содержит минимум три поля: значение узла, указатель на начало списка потомков узла, указатель на следующий элемент в списке потомков текущего уровня. Также как и для бинарного дерева необходимо хранить указатель на корень дерева. При этом дерево представлено в виде структуры, связывающей списки потомков различных вершин. Такой способ представления вполне пригоден и для бинарных деревьев.

Применение сильноветвящихся деревьев
Один из примеров применения сильноветвящихся деревьев был связан с представлением арифметических выражений произвольного вида. Рассмотрим использование таких деревьев для представления иерархической структуры каталогов файловой системы. Во многих файловых системах структура каталогов и файлов, как правило, представляет собой одно или несколько сильноветвящихся деревьев. В файловой системе MS Dos корень дерева соответствует логическому диску. Листья дерева соответствуют файлам и пустым каталогам, а узлы с ненулевой степенью - непустым каталогам.

Сокращенный обход право-прошитого бинарного дерева Сокращенный обход бинарного дерева — разновидность обхода бинарного дерева поиска, позволяющая, используя O(1) дополнительной памяти, обходить все элементы дерева за O(N), где N — количество элементов в дереве. При этом каждый элемент дерева будет просмотрен не больше двух раз. Прошитое дерево В общем случае это обычное бинарное дерево, ссылки "лево" и "право" которого вместо того, чтобы равняться null ссылаются на своего "родителя". Таким образом деревья можно пробегать быстрее. Для того, чтобы распознать где нормальная ссылка, а где ссылка на родителя используют дополнительные одну-две переменные в которой хранится данная информация. Рассмотрим разновидность бинарного дерева поиска. В каждом узле которого, кроме ссылок left, right и parent будем ещё хранить ссылку uplink. Ссылка uplink каждого узла дерева должна удовлетворять следующим свойствам: если right ≠ null, то uplink = null; если right = null, то uplink указывает на элемент следующий по величине, если таковой существует. У наибольшего элемента дерева uplink = null, также как и right = null. Ссылки left, right имеют то же значение, что и у обычного бинарного дерева поиска. Операция обхода дерева Операция обхода прошитого дерева позволяет перечислить все элементы дерева в порядке возрастания ключа за время O(N) и используя O(1) дополнительной памяти. Операцию обхода прошитого дерева реализуем следующим образом. В качестве стартового элемента возьмем минимальный элемент дерева. Рассмотрим текущий элемент. Если right ≠ null, то следующий по величине элемент за текущим будет минимальный элемент в нашем правом поддереве. Если right = null, то следующий по величине элемент будет элемент uplink. Согласно определению uplink. Если и right = null и uplink = null, то текущий элемент в дереве имеет наибольший ключ и обход дерева можно завершить. Заметим, что при этом каждый элемент будет просмотрен не больше чем два раза: первый раз при движении к минимальному элементу в правом поддереве некого элемента, а второй раз при переходе по uplink. Т.к. каждый элемент будет просмотрен не больше чем константу раз, а количество элементов N, то время работы алгоритма есть O(N). Операция вставки в дерево Операция вставки является аналогичной операции вставки в обычное бинарное дерево поиска, но требует дополнительной корректировки поля uplink. У только что вставленного узла, обозначим его n, поле right = null. Значит uplink должен содержать ссылку на следующий по величине элемент после нашего. Если n — левый сын своего родителя, то следующий по величине за ним элемент будет его родитель. Если n — стал правым сыном своего родителя, то это означает, что у его родителя uplink ≠ null и указывает на следующий после его родителя элемент. Поэтому нам необходимо uplink родителя записать узлу n, а uplink родителя обнулить. Операция вставки в прошитое дерево выполняет на константу операций больше чем в простое бинарное дерево, поэтому работает также O(logN). Операция удаления из дерева Операция удаления, также как и вставки, реализуется аналогично удалению из бинарного дерева поиска, только необходимо соответствующим образом откорректировать поля uplink. Предположим, что в дереве необходимо удалить некий элемент e. Рассмотрим четыре случая. Пусть e лист. Если e является левым сыном своего родителя, то мы можем просто удалить этот элемент из дерева. Если e — правый сын своего родителя, то мы должны наш uplink записать нашему родителю, а затем удалить элемент. Пусть e имеет только правого потомка. Тогда операция удаления e является полностью аналогичной операции удаления из бинарного дерева. Пусть e имеет только левого потомка. Запишем нашего потомка на место удаляемого узла. Т.к. uplink наибольшего элемента в нашем левом поддереве ссылается на элемент e необходимо его модифицировать, чтобы теперь он ссылался на нашего левого потомка. Пусть e имеет обоих потомков. По аналогии с обычным бинарным деревом, найдем следующий (обозначим его f) за удаляемым элемент (это будет наименьший элемент в его правом поддереве), перепишем содержимое элемента f в элемент e. И попробуем удалить f. Т.к. узел f максимум может содержать только одного потомка, то при его удалении могут иметь место только первые три случая. Несложно показать, что операция удаления элемента из прошитого дерева, также будет выполняться за O(logN), где N — количество элементов в дереве. Операция поиска Операция поиска также может быть реализована на прошитом дереве. При этом она будет полностью эквивалентна операции поиска в бинарном дереве. Поэтому она не представляет интереса.

Чтобы прошить дерево - представляем его в бинарном виде. Делается это просто. У нас уже есть корень, его ссылка налево будет первое поддерево, а ссылкой направо будет указатель на все остальные. Повторяем процедуру до тех пор, пока не исчерпаем все деревья.

Сокращенный обход право-прошитого бинарного дерева
Сокращенный обход бинарного дерева — разновидность обхода бинарного дерева поиска, позволяющая, используя O(1) дополнительной памяти, обходить все элементы дерева за O(N), где N — количество элементов в дереве. При этом каждый элемент дерева будет просмотрен не больше двух раз.
Прошитое дерево
В общем случае это обычное бинарное дерево, ссылки "лево" и "право" которого вместо того, чтобы равняться null ссылаются на своего "родителя". Таким образом деревья можно пробегать быстрее. Для того, чтобы распознать где нормальная ссылка, а где ссылка на родителя используют дополнительные одну-две переменные в которой хранится данная информация.
Рассмотрим разновидность бинарного дерева поиска. В каждом узле которого, кроме ссылок left, right и parent будем ещё хранить ссылку uplink. Ссылка uplink каждого узла дерева должна удовлетворять следующим свойствам:
если right ≠ null, то uplink = null;
если right = null, то uplink указывает на элемент следующий по величине, если таковой существует.

У наибольшего элемента дерева uplink = null, также как и right = null.

Ссылки left, right имеют то же значение, что и у обычного бинарного дерева поиска.
Операция обхода дерева
Операция обхода прошитого дерева позволяет перечислить все элементы дерева в порядке возрастания ключа за время O(N) и используя O(1) дополнительной памяти.

Операцию обхода прошитого дерева реализуем следующим образом. В качестве стартового элемента возьмем минимальный элемент дерева. Рассмотрим текущий элемент. Если right ≠ null, то следующий по величине элемент за текущим будет минимальный элемент в нашем правом поддереве. Если right = null, то следующий по величине элемент будет элемент uplink. Согласно определению uplink. Если и right = null и uplink = null, то текущий элемент в дереве имеет наибольший ключ и обход дерева можно завершить.

Заметим, что при этом каждый элемент будет просмотрен не больше чем два раза: первый раз при движении к минимальному элементу в правом поддереве некого элемента, а второй раз при переходе по uplink. Т.к. каждый элемент будет просмотрен не больше чем константу раз, а количество элементов N, то время работы алгоритма есть O(N).
Операция вставки в дерево

Операция вставки является аналогичной операции вставки в обычное бинарное дерево поиска, но требует дополнительной корректировки поля uplink. У только что вставленного узла, обозначим его n, поле right = null. Значит uplink должен содержать ссылку на следующий по величине элемент после нашего. Если n — левый сын своего родителя, то следующий по величине за ним элемент будет его родитель. Если n — стал правым сыном своего родителя, то это означает, что у его родителя uplink ≠ null и указывает на следующий после его родителя элемент. Поэтому нам необходимо uplink родителя записать узлу n, а uplink родителя обнулить. Операция вставки в прошитое дерево выполняет на константу операций больше чем в простое бинарное дерево, поэтому работает также O(logN).
Операция удаления из дерева

Операция удаления, также как и вставки, реализуется аналогично удалению из бинарного дерева поиска, только необходимо соответствующим образом откорректировать поля uplink. Предположим, что в дереве необходимо удалить некий элемент e. Рассмотрим четыре случая.

Пусть e лист. Если e является левым сыном своего родителя, то мы можем просто удалить этот элемент из дерева. Если e — правый сын своего родителя, то мы должны наш uplink записать нашему родителю, а затем удалить элемент.

Пусть e имеет только правого потомка. Тогда операция удаления e является полностью аналогичной операции удаления из бинарного дерева.

Пусть e имеет только левого потомка. Запишем нашего потомка на место удаляемого узла. Т.к. uplink наибольшего элемента в нашем левом поддереве ссылается на элемент e необходимо его модифицировать, чтобы теперь он ссылался на нашего левого потомка.

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

Несложно показать, что операция удаления элемента из прошитого дерева, также будет выполняться за O(logN), где N — количество элементов в дереве.
Операция поиска
Операция поиска также может быть реализована на прошитом дереве. При этом она будет полностью эквивалентна операции поиска в бинарном дереве. Поэтому она не представляет интереса.

AVL-деревья имеют структуру, похожую на бинарные деревья поиска. Все операции идентичны описанным для бинарных деревьев, за исключением методов Insert и Delete, которые должны постоянно отслеживать соотношение высот левого и правого поддеревьев узла. Для сохранения этой информации мы расширили определение объекта TreeNode, включив поле balanceFactor (показатель сбалансированности), которое содержит разность высот правого и левого поддеревьев.

balanceFactor = height(right subtree) - height(left subtree)

Алгоритм AVL-вставки

Процесс вставки почти такой же, что и для бинарного дерева поиска. Осуществляется рекурсивный спуск по левым и правым сыновьям, пока не встретится пустое поддерево, а затем производится пробная вставка нового узла в этом месте. В течение этого процесса мы посещаем каждый узел на пути поиска от корневого к новому элементу.

Поскольку процесс рекурсивный, обработка узлов ведется в обратном порядке. При этом показатель сбалансированности родительского узла можно скорректировать после изучения эффекта от добавления нового элемента в одно из поддеревьев. Необходимость корректировки определяется для каждого узла, входящего в поисковый маршрут. Есть три возможных ситуации. В двух первых случаях узел сохраняет сбалансированность и реорганизация поддеревьев не требуется. Нужно лишь скорректировать показатель сбалансированности данного узла. В третьем случае разбалансировка дерева требует одинарного или двойного поворотов узлов.

Случай 1. Узел на поисковом маршруте изначально является сбалансированным (balanceFactor = 0). После вставки в поддерево нового элемента узел стал перевешивать влево или вправо в зависимости от того, в какое поддерево была произведена вставка. Если элемент вставлен в левое поддерево, показателю сбалансированности присваивается -1, а если в правое, то 1. Например, на пути 40-50-60 каждый узел сбалансирован. После вставки узла 55 показатели сбалансированности изменяются.

Случай 2. Одно из поддеревьев узла перевешивает, и новый узел вставляется в более легкое поддерево. Узел становится сбалансированным. Сравните, например, состояния дерева до и после вставки узла 55.

Случай 3. Одно из поддеревьев узла перевешивает, и новый узел помещается в более тяжелое поддерево. Тем самым нарушается условие сбалансированности, так как balanceFactor выходит за пределы -1..1. Чтобы восстановить равновесие, нужно выполнить поворот.

template <class T>
void AVLTree<T>::AVLInsert(AVLTreeNode<T>* &tree,
AVLTreeNode<T>* newNode, int &reviseBalanceFactor)
{
// флаг "Показатель сбалансированности был изменен"
int rebalanceCurrNode;

// встретилось пустое поддерево. Пора вставлять новый узел
if (tree == NULL)
{
// вставить новый узел
tree = newNode;

// объявить новый узел сбалансированным
tree->balanceFactor = balanced;

// сообщить об изменении показателя сбалансированности
reviseBalanceFactor = 1;
}
// рекурсивно спускаться по левому поддереву, если новый узел меньше текущего
else if (newNode->data < tree->data)
{
AVLInsert(tree->Left(), newNode, rebalanceCurrNode);
// проверить, нужно ли корректировать balanceFactor
if (rebalanceCurrNode)
{
// вставка слева от узла, перевешивающего влево. будет нарушено
// условие сбалансированности; выполнить поворот (случай 3)
if (tree->balanceFactor == leftheavy)
UpdateLeftTree(tree, reviseBalanceFactor);

// вставка слева от сбалансированного узла.
// узел станет перевешивать влево (случай 1)
else if (tree->balanceFactor == balanced)
{
tree->balanceFactor = leftheavy;
reviseBalanceFactor = 1;
}
// вставка слева от узла, перевешивающего вправо.
// узел станет сбалансированным (случай 2)
else
{
tree->balanceFactor = balanced;
reviseBalanceFactor = 0;
}
}
else
// перебалансировка не требуется. не опрашивать предыдущие узлы
reviseBalanceFactor = 0;
}
// иначе рекурсивно спускаться по правому поддереву
else if (newNode->data < tree->data)
{
AVLInsert(tree->Right(), newNode, rebalanceCurrNode);
// проверить, нужно ли корректировать balanceFactor
if (rebalanceCurrNode)
{
// вставка справа от узла, перевешивающего вправо. будет нарушено
// условие сбалансированности; выполнить поворот (случай 3)
if (tree->balanceFactor == rightheavy)
UpdateRightTree(tree, reviseBalanceFactor);

// вставка справа от сбалансированного узла.
// узел станет перевешивать вправо (случай 1)
else if (tree->balanceFactor == balanced)
{
tree->balanceFactor = rightheavy;
reviseBalanceFactor = 1;
}
// вставка справа от узла, перевешивающего влево.
// узел станет сбалансированным (случай 2)
else
{
tree->balanceFactor = balanced;
reviseBalanceFactor = 0;
}
}
else
// перебалансировка не требуется. не опрашивать предыдущие узлы
reviseBalanceFactor = 0;
}
}

Алгоритм удаления вершины

Для простоты опишем рекурсивный алгоритм удаления. Если вершина - лист, то удалим её и вызовем балансировку всех её предков в порядке от родителя к корню. Иначе найдём самую близкую по значению вершину в поддереве наибольшей высоты (правом или левом) и переместим её на место удаляемой вершины, при этом вызвав процедуру её удаления.
Докажем, что данный алгоритм сохраняет балансировку. Для этого докажем по индукции по высоте дерева, что после удаления некоторой вершины из дерева и последующей балансировки высота дерева уменьшается не более, чем на 1. База индукции: Для листа очевидно верно. Шаг индукции: Либо условие балансированности в корне (после удаления корень может изменится) не нарушилось, тогда высота данного дерева не изменилась, либо уменьшилось строго меньшее из поддеревьев => высота до балансировки не изменилась => после уменьшится не более чем на 1.
Очевидно, в результате указанных действий процедура удаления вызывается не более 3 раз, так как у вершины, удаляемой по 2-му вызову, нет одного из поддеревьев. Но поиск ближайшего каждый раз требует O(N) операций, отсюда видна очевидная оптимизация: поиск ближайшей вершины производится по краю поддерева. Отсюда количество действий O(lg(N)).

Красно-черные деревья

Красно-черные деревья - один из способов балансировки деревьев. Название происходит от стандартной раскраски узлов таких деревьев в красный и черный цвета. Цвета узлов используются при балансировке дерева. Во время операций вставки и удаления поддеревья может понадобиться повернуть, чтобы достигнуть сбалансированности дерева. Оценкой как среднего время, так и наихудшего является O(log n).

Теория

Красно-черное дерево - это бинарное дерево с следующими свойствами:
Каждый узел покрашен либо в черный, либо в красный цвет.
Листьями объявляются NIL-узлы (т.е. "виртуальные" узлы, наследники узлов, которые обычно называют листьями; на них "указывают" NULL указатели). Листья покрашены в черный цвет.
Если узел красный, то оба его потомка черны.
На всех ветвях дерева, ведущих от его корня к листьям, число черных узлов одинаково.
Количество черных узлов на ветви от корня до листа называется черной высотой дерева. Перечисленные свойства гарантируют, что самая длинная ветвь от корня к листу не более чем вдвое длиннее любой другой ветви от корня к листу. Чтобы понять, почему это так, рассмотрим дерево с черной высотой 2. Кратчайшее возможное расстояние от корня до листа равно двум - когда оба узла черные. Длиннейшее расстояние от корня до листа равно четырем - узлы при этом покрашены (от корня к листу) так: красный, черный, красный, черный. Сюда нельзя добавить черные узлы, поскольку при этом нарушится свойство 4, из которого вытекает корректность понятия черной высоты. Поскольку согласно свойству 3 у красных узлов непременно черные наследники, в подобной последовательности недопустимы и два красных узла подряд. Таким образом, длиннейший путь, который мы можем сконструировать, состоит из чередования красных и черных узлов, что и приводит нас к удвоенной длине пути, проходящего только через черные узлы. Все операции над деревом должны уметь работать с перечисленными свойствами. В частности, при вставке и удалении эти свойства должны сохраниться.

Вставка

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

Красный предок, красный "дядя": Ситуацию красный-красный иллюстрирует рис. 1. У нового узла X предок и "дядя" оказались красными. Простое перекрашивание избавляет нас от красно-красного нарушения. После перекраски нужно проверить "дедушку" нового узла (узел B), поскольку он может оказаться красным. Обратите внимание на распространение влияния красного узла на верхние узлы дерева. В самом конце корень мы красим в черный цвет корень дерева. Если он был красным, то при этом увеличивается черная высота дерева.

Красный предок, черный "дядя": На рис. 2 представлен другой вариант красно-красного нарушения - "дядя" нового узла оказался черным. Здесь узлы может понадобиться вращать, чтобы скорректировать поддеревья. В этом месте алгоритм может остановиться из-за отсутствия красно-красных конфликтов и вершина дерева (узел A) окрашивается в черный цвет. Обратите внимание, что если узел X был в начале правым потомком, то первым применяется левое вращение, которое делает этот узел левым потомком.
Каждая корректировка, производимая при вставке узла, заставляет нас подняться в дереве на один шаг. В этом случае до остановки алгоритма будет сделано 1 вращение (2, если узел был правым потомком). Метод удаления аналогичен.

Рис. 1: Вставка - Красный предок, красный "дядя

Рис. 2: Вставка - красный предок, черный "дядя"

рисунки здесь http://www.algolist.manual.ru/ds/rbtree.php

Реализация

Операторы typedef T, а также сравнивающие compLT и compEQ следует изменить так, чтобы они соответствовали данным, хранимым в узлах дерева. В каждом узле типа Node хранятся указатели left, right на двух потомков и parent на предка. Цвет узла хранится в поле color и может быть либо RED, либо BLACK. Собственно данные хранятся в поле data. Все листья дерева являются "сторожевыми" (sentinel), что сильно упрощает коды. Узел root является корнем дерева и в самом начале является сторожевым.
Функция insertNode запрашивает память под новый узел, устанавливает нужные значения его полей и вставляет в дерево. Соответственно, она вызывает insertFixup, которая следит за сохранением красно-черных свойств. Функция deleteNode удаляет узел из дерева. Она вызывает deleteFixup, которая восстанавливает красно-черные свойства. Функция findNode ищет в дереве нужный узел.

/* red-black tree */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>

typedef int T; /* type of item to be stored */
#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)

/* Red-Black tree description */
typedef enum { BLACK, RED } nodeColor;

typedef struct Node_ {
struct Node_ *left; /* left child */
struct Node_ *right; /* right child */
struct Node_ *parent; /* parent */
nodeColor color; /* node color (BLACK, RED) */
T data; /* data stored in node */
} Node;

#define NIL &sentinel /* all leafs are sentinels */
Node sentinel = { NIL, NIL, 0, BLACK, 0};

Node *root = NIL; /* root of Red-Black tree */

void rotateLeft(Node *x) {

/**************************
* rotate node x to left *
**************************/

Node *y = x->right;

/* establish x->right link */
x->right = y->left;
if (y->left != NIL) y->left->parent = x;

/* establish y->parent link */
if (y != NIL) y->parent = x->parent;
if (x->parent) {
if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
} else {
root = y;
}

/* link x and y */
y->left = x;
if (x != NIL) x->parent = y;
}

void rotateRight(Node *x) {

/****************************
* rotate node x to right *
****************************/

Node *y = x->left;

/* establish x->left link */
x->left = y->right;
if (y->right != NIL) y->right->parent = x;

/* establish y->parent link */
if (y != NIL) y->parent = x->parent;
if (x->parent) {
if (x == x->parent->right)
x->parent->right = y;
else
x->parent->left = y;
} else {
root = y;
}

/* link x and y */
y->right = x;
if (x != NIL) x->parent = y;
}

void insertFixup(Node *x) {

/*************************************
* maintain Red-Black tree balance *
* after inserting node x *
*************************************/

/* check Red-Black properties */
while (x != root && x->parent->color == RED) {
/* we have a violation */
if (x->parent == x->parent->parent->left) {
Node *y = x->parent->parent->right;
if (y->color == RED) {

/* uncle is RED */
x->parent->color = BLACK;
y->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
} else {

/* uncle is BLACK */
if (x == x->parent->right) {
/* make x a left child */
x = x->parent;
rotateLeft(x);
}

/* recolor and rotate */
x->parent->color = BLACK;
x->parent->parent->color = RED;
rotateRight(x->parent->parent);
}
} else {

/* mirror image of above code */
Node *y = x->parent->parent->left;
if (y->color == RED) {

/* uncle is RED */
x->parent->color = BLACK;
y->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
} else {

/* uncle is BLACK */
if (x == x->parent->left) {
x = x->parent;
rotateRight(x);
}
x->parent->color = BLACK;
x->parent->parent->color = RED;
rotateLeft(x->parent->parent);
}
}
}
root->color = BLACK;
}

Node *insertNode(T data) {
Node *current, *parent, *x;

/***********************************************
* allocate node for data and insert in tree *
***********************************************/

/* find where node belongs */
current = root;
parent = 0;
while (current != NIL) {
if (compEQ(data, current->data)) return (current);
parent = current;
current = compLT(data, current->data) ?
current->left : current->right;
}

/* setup new node */
if ((x = malloc (sizeof(*x))) == 0) {
printf ("insufficient memory (insertNode)\n");
exit(1);
}
x->data = data;
x->parent = parent;
x->left = NIL;
x->right = NIL;
x->color = RED;

/* insert node in tree */
if(parent) {
if(compLT(data, parent->data))
parent->left = x;
else
parent->right = x;
} else {
root = x;
}

insertFixup(x);
return(x);
}

void deleteFixup(Node *x) {

/*************************************
* maintain Red-Black tree balance *
* after deleting node x *
*************************************/

while (x != root && x->color == BLACK) {
if (x == x->parent->left) {
Node *w = x->parent->right;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rotateLeft (x->parent);
w = x->parent->right;
}
if (w->left->color == BLACK && w->right->color == BLACK) {
w->color = RED;
x = x->parent;
} else {
if (w->right->color == BLACK) {
w->left->color = BLACK;
w->color = RED;
rotateRight (w);
w = x->parent->right;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->right->color = BLACK;
rotateLeft (x->parent);
x = root;
}
} else {
Node *w = x->parent->left;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rotateRight (x->parent);
w = x->parent->left;
}
if (w->right->color == BLACK && w->left->color == BLACK) {
w->color = RED;
x = x->parent;
} else {
if (w->left->color == BLACK) {
w->right->color = BLACK;
w->color = RED;
rotateLeft (w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->left->color = BLACK;
rotateRight (x->parent);
x = root;
}
}
}
x->color = BLACK;
}

void deleteNode(Node *z) {
Node *x, *y;

/*****************************
* delete node z from tree *
*****************************/

if (!z || z == NIL) return;

if (z->left == NIL || z->right == NIL) {
/* y has a NIL node as a child */
y = z;
} else {
/* find tree successor with a NIL node as a child */
y = z->right;
while (y->left != NIL) y = y->left;
}

/* x is y's only child */
if (y->left != NIL)
x = y->left;
else
x = y->right;

/* remove y from the parent chain */
x->parent = y->parent;
if (y->parent)
if (y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
else
root = x;

if (y != z) z->data = y->data;

if (y->color == BLACK)
deleteFixup (x);

free (y);
}

Node *findNode(T data) {

/*******************************
* find node containing data *
*******************************/

Node *current = root;
while(current != NIL)
if(compEQ(data, current->data))
return (current);
else
current = compLT (data, current->data) ?
current->left : current->right;
return(0);
}

void main(int argc, char **argv) {
int a, maxnum, ct;
Node *t;

/* command-line:
*
* rbt maxnum
*
* rbt 2000
* process 2000 records
*
*/

maxnum = atoi(argv[1]);

for (ct = maxnum; ct; ct--) {
a = rand() % 9 + 1;
if ((t = findNode(a)) != NULL) {
deleteNode(t);
} else {
insertNode(a);
}
}
}

Важным для информатики классом двоичных деревьев являются деревья арифметических выражений с бинарными и унитарными операциями, где каждой операции соответствует вершина, поддеревьями которой являются ее операнды.
Обходя дерево выражений (a+b/c)*(d-e*f) разными способами, мы получаем три различные очереди вершин:
КЛП * + a / b c - d *e f ;
ЛКП a+b / c * d - e * f;
ЛПК a b c / + d e f * - *
которые представляют собой ни что иное, как широко используемые в информатике различные формы записи выражений: префикстную (ассемблер, код операции перед (pre) операндами, называемую также польской), привычную инфикстную (математичекую, знак операции между (in) операндами), но без скобок, задающих порядок выполнения операций, и постфикстную (обратную польскую). Бесскобочная форма записи представляет собой линейную последовательность действий, пригодную для выполнения обычных фон Неймановским компьютером.

Алгоритм Рутисхаузера

Данный алгоритм является одним из наиболее ранних. Его особенностью является предположение о полной скобочной структуре выражения. Под полной скобочной записью выражения понимается запись, в которой порядок действий задается расстановкой скобок. Неявное старшинство операций при этом не учитывается. Например:
D:=((C-(B*L))+K)

Обрабатывая выражение с полной скобочной структурой, алгоритм присваивает каждому символу из строки номер уровня по следующему пpавилу:

1. если это откpывающаяся скобка или пеpеменная, то значение увеличивается на 1;

2. если знак опеpации или закpывающаяся скобка, то уменьшается на 1.

Для выражения (А+(В+С)) присваивание значений уровня будет происходить следующим образом :
|-------|---------------------------------------|
|N симв.| 1 2 3 4 5 6 7 8 9 |
|-------|---------------------------------------|
|Символы| |
|строки | ( A + ( B * C ) ) |
|-------|---------------------------------------|
|Номера | |
|уровней| 1 2 1 2 3 2 3 2 1 |
|-------|---------------------------------------|

Алгоритм складывается из следующих шагов:

1. выполнить расстановку уровней;

2. выполнить поиск элементов строки с максимальным значением уровня;

3. выделить тройку - два операнда с максимальным значением уровня и операцию, которая заключена между ними;

4. результат вычисления тройки обозначить вспомогательной переменной;

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

6. выполнять п.п.2 - 5 до тех пор, пока во входной строке не останется одна переменная, обозначающая общий результат выражения.
Пример разбора :

|-----------------|-----------------------------------------------|
|Генерируемые| Выражение |
| тройки | |
|-----------------|-----------------------------------------------|
| | ( ( ( ( А + В ) * С ) / D ) - E ) |
| | 0 1 2 3 4 5 4 5 4 3 4 3 2 3 2 1 2 1 0 |
| | |
|+ А В - > R | ( ( ( R * C ) / D ) - E ) |
| | 0 1 2 3 4 3 4 3 2 3 2 1 2 1 0 |
| | |
|* R C -> S | ( ( S / D ) - E ) |
| | 0 1 2 3 2 3 2 1 2 1 0 |
| | |
|-----------------|-----------------------------------------------|

|------------------|-----------------------------------|
|Генерируемые | Выражение |
| тройки | |
|------------------|-----------------------------------|
|/ S D -> Q | ( Q - E ) |
| | 0 1 2 1 2 1 0 |
| | |
|- Q E -> T | T |
|------------------|-----------------------------------|

А построение дерева покажу завтра на пальцах =)
)))

Эдскер Дейкстра изобрёл алгоритм для преобразования выражений из инфиксной нотации в ОПН. Алгоритм получил название «сортировочная станция», за сходство его операций с происходящим на железнодорожных сортировочных станциях. Инфиксная нотация — это форма математических записей, которую использует большинство людей (например, 3 + 4 или 3 + 4 * (2 - 1)). Как и алгоритм вычисления ОПН, алгоритм сортировочной станции основан на стеке. В преобразовании участвуют две текстовых переменных: входная и выходная строки. В процессе преобразования используется стек, хранящий ещё не добавленные к выходной строке операторы. Преобразующая программа читает входную строку последовательно символ за символом (символ — это не обязательно буква), выполняет на каждом шаге некоторые действия в зависимости от того, какой символ был прочитан.

Алгоритм построение постфиксной записи из инфиксной(обычной)
Пока есть ещё символы для чтения:
Читаем очередной символ.
Если символ является числом, добавить его к выходной строке.
Если символ является символом функции, помещаем его в стек.
Если символ является разделителем аргументов функции (то есть, запятая):
До тех пор, пока верхним элементом стека не станет открывающаяся скобка, выталкиваем элементы из стека в выходную строку. Если открывающаяся скобка не встретилась, это означает, что в выражении либо неверно поставлен разделитель, либо несогласованы скобки.
Если символ является оператором, о1, тогда:
1) пока…
… (если оператор o1 ассоциированный, либо лево-ассоциированный) приоритет o1 меньше либо равен приоритету оператора, находящегося на вершине стека…
… (если оператор o1 право-ассоциированый) приоритет o1 меньше приоритета оператора, находящегося на вершине стека…
… выталкиваем верхние элементы стека c бо́льшим либо равным приоритетом в выходную строку;
2) помещаем оператор o1 в стек.
Если символ является открывающейся скобкой, помещаем его в стек.
Если символ является закрывающейся скобкой, выталкиваем элементы из стека в выходную строку до тех пор, пока на вершине стека не окажется открывающаяся скобка. При этом открывающаяся скобка удаляется из стека, но в выходную строку не добавляется. Если после этого шага на вершине стека оказывается символ функции, выталкиваем его в выходную строку. Если стек закончился раньше, чем мы встретили открывающуюся скобку, это означает, что в выражении несогласованы скобки.
Когда входная строка закончилась, вытолкнуть все символы из стека в выходную строку. (В стеке должны были остаться только символы операторов; если это не так, значит в выражении несогласованы скобки.)

Простой пример

Вход: 3 + 4

Добавим 3 к выходной строке (если прочитано число, то оно сразу добавляется к выходной строке).

Помещаем + (или его Идентификатор) в стек операторов.

Добавим 4 к выходной строке.

Мы прочитали всё выражение, теперь выталкиваем все оставшиеся в стеке операторы в выходную строку. В нашем примере в стеке содержится только +.

Выходная строка: 3 4 +

В данном примере проявляются некоторые правила: все числа переносятся в выходную строку сразу после прочтения; когда выражение прочитано полностью, все оставшиеся в стеке операторы выталкиваются в выходную строку.

Сложный пример
Приоритеты:
• ^ высокий
• * / средний
• + - низкий

Вход: 3 + 4 * 2 / (1 - 5)^2

Читаем «3»
Добавим «3» к выходной строке
Выход: 3

Читаем «+»
Кладём «+» в стек
Выход: 3
Стек: +

Читаем «4»
Добавим «4» к выходной строке
Выход: 3 4
Стек: +

Читаем «*»
Кладём «*» в стек
Выход: 3 4
Стек: + *

Читаем «2»
Добавим «2» к выходной строке
Выход: 3 4 2
Стек: + *

Читаем «/»
Выталкиваем «*» из стека в выходную строку, кладём «/» в стек
Выход: 3 4 2 *
Стек: + /

Читаем «(»
Кладём «(» в стек
Выход: 3 4 2 *
Стек: + / (

Читаем «1»
Добавим «1» к выходной строке
Выход: 3 4 2 * 1
Стек: + / (

Читаем «-»
Кладём «-» в стек
Выход: 3 4 2 * 1
Стек: + / ( -

Читаем «5»
Добавим «5» к выходной строке
Выход: 3 4 2 * 1 5
Стек: + / ( -

Читаем «)»
Выталкиваем «-» из стека в выходную строку, выталкиваем «(»
Выход: 3 4 2 * 1 5 -
Стек: + /

Читаем «^»
Кладём «^» в стек
Выход: 3 4 2 * 1 5 -
Стек: + / ^

Читаем «2»
Добавим «2» к выходной строке
Выход: 3 4 2 * 1 5 - 2
Стек: + / ^

Конец выражения
Выталкиваем все элементы из стека в строку
Выход: 3 4 2 * 1 5 - 2 ^ / +

Алгоритм построения дерева из постфиксной записи
1) Если не достигнут конец строки ввода, прочитать очередной символ.
2) Создать новую вершину дерева, записать в нее этот символ.
3) Если символ - операция, то:
1) вызвать алгоритм Prefix для левого поддерева;
2) вызвать алгоритм Prefix для правого поддерева.