Двоичные деревья

Какие бывают двоичные деревья

- двочиные дервья поиска.
- для вычесления префиксных, суфискных операций.
- другие алгоритмы (например дерево Хаффмана для шифрования).
- пирамида

Зачем их использовать ?

Поиск занимает logN, правда, как следсвтие другие операции - вставка, удаление тоже logN. Понятно, что в обычном списке операция поиска занимает N. В

Обход двоичного дерева

Симметричный обход
Прямой обход
Обратный обход

Обход - простейший рекурсивный алгоритм, типа
1) Вызов самого себя для обхода левого поддерева узла
2) Посещение узла
3) Вызов самого себя для обхода правого поддерева узла

Разница в трех обходах упомянутых выше - всего лишь порядок операций.

Пирамида

Пирамида - это двоичное дерево. Обаладет след. характеристиками.

1) Все уровни дерева содержат все возможные узлы ( хотя последний может быть заполнен лишь частично)
2) Обычно реализуется на базе массива.
3) Ключ каждого узла больше (либо равен) ключей его потомков.

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

Сбалансированные двоичные деревья

Для того, чтоб операция поиска всегда занимала время logN, дерево должно быть сбалансировано.

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

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

AVL деревья
Из всех разновидностей сбалансированных деревьев, первым появилось AVL дерево. В AVL деревьях в каждом узле хранится дополнительная информация: разность весов левого и правого поддеревьев. Это разность не может быть больше 1. После вставки нового узла выполняется одиночный или двойной поворот для выравниания высот. Затем алгоритм двигается вверх и проверяет узел, выравнивает высоты в случае необходимости. И так до корня. Поиск в AVL дереве выполняется за logN, однако вставка и удаление требует двух проходов от корня до узла, и от узла до корня. Поэтому эти деревья уступают красно-черным деревьям и используются редко.