Балансировать тройное поисковое дерево

Question

Как можно «балансировать» тройное поисковое дерево? Большинство реализаций TST не касаются балансировки, но предлагают вставить в оптимальный заказ (который я не могу контролировать.)

Answer 1

Статья в докторе Доббсе о Тройные поисковые деревья говорит: DD Sleator и RE Tarjan описывают теоретические алгоритмы балансировки для тройных поисковых деревьев в «саморегулирующих бинарных деревьях поиска» (Journal of the ACM, июль 1985 г.). Вы можете найти онлайн -версии этой статьи с вашей любимой поисковой системой.

Answer 2

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

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

Answer 3

Обобщением бинарного дерева поиска является B-дерево, который работает для фанатов в любом месте от 2 и старше. Это не единственный способ сделать это, но это обычный.

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

Answer 4

Прочитайте эту статью:

«Саморегулирование тройного поиска пытается с использованием условных вращений и рандомизированной эвристики» от «Гада Хан-Бадр ∗ и B. John Oommen †»

Это поможет вам понять саморегулирование и баланс TST.