Балансировка троичного поискового дерева
Как можно "сбалансировать" троичное дерево поиска? Большинство реализаций tst не учитывают балансировку, но предлагают вставку в оптимальном порядке (что я не могу контролировать.)
4 ответа
Статья доктора Доббса о троичных поисковых деревьях гласит: Д. Д. Слеатор и Р. Э. Тарьян описывают теоретические алгоритмы балансировки для троичных поисковых деревьев в "Саморегулирующихся деревьях двоичного поиска" (Журнал ACM, июль 1985 г.). Вы можете найти онлайн версии этого документа с вашей любимой поисковой системой.
Одна простая оптимизация состоит в том, чтобы сделать его красно-черным деревом, которое может избежать некоторых наихудших сценариев. TST на самом деле являются просто двоичными деревьями, где значением данного узла является другой TST. Таким образом, "средний" дочерний элемент узла на самом деле не является частью дерева, которое балансируется на каждом уровне, так как он все равно не может перейти к другому родительскому элементу.
Это гарантирует, что каждый уровень дерева пройден в журнале (R), хотя вы, вероятно, могли бы сделать еще лучше, принимая во внимание размер подзапросов в каждом узле. Это выглядит намного сложнее, хотя!
Прочитайте эту статью:
"Саморегулирование попыток троичного поиска с использованием условных вращений и рандомизированной эвристики" от "Ghada Hany Badr∗ и B. John Oommen †"
это поможет вам понять самонастраивающиеся и уравновешивающие TST.
Обобщением бинарного дерева поиска является B-дерево, которое работает для разветвлений от 2 и выше. Это не единственный способ сделать это, но это распространенный способ.
Примерно так это работает, если вставка или удаление выводят дерево из равновесия, оно крадет элемент или пространство из соседнего узла. Если даже этого недостаточно для поддержания баланса дерева, его высота будет изменена, чтобы освободить место.