ВИДЫ СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ, ДОСТОИНСТВА И НЕДОСТАТКИ.

Виды деревьев	Достоинства	Недостатки
Дерево поиска	Простота операции поиска, вставки, удаления	Не сбалансированное
Идеально сбалансированное дерево	Наименьшее возможное время поиска = O(log N)	Нет операции вставки и удаления
АВЛ	Поиск, вставка, удаление за O(log N)	Необходимость выполнять операции балансировки
Красно-черные (= СДБ)	См. СДБ	См. СДБ
Б-дерево	Возможность создания очень больших разветвленных деревьев	Требуются обращения ко вторичной памяти
ДБ-деревья		Хуже, чем СДБ
Дерево оптимального поиска	Оптимальный поиск при различных вероятностях ключей (чем больше вероятность, тем ближе к корню)	Нет операций вставки и удаления; Сложность построения O()
Splay-дерево	Сбалансированно Время операций O(log N)	Могут вырождаться в линеный список

Не нашли, что искали? Воспользуйтесь поиском: