0

Не могу понять, что такое балансировка, а конкретнее как ее реализовать в программе для троичного дерева. Каков вообще ее алгоритм?

Вот есть у меня готовое троичное дерево, как мне теперь сделать для него балансировку?

0

1 ответ 1

4

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

Пример:

        30
      /    \
     20     40
    / \      
   10  25  
  /  \
 5    15

При такой организации длина левой ветки больше правой (в этом примере на 2, но в реальных наборах данных длина может отличаться куда больше). А это значит, (в практическом смысле, например), что поиск элемента с ключом "5" займёт больше времени, чем поиск элемента с ключом "40".

Цель балансировки - организовать дерево так, чтобы длины веток (или глубина дерева, etc) при разных наборах данных были схожи. Например, вот это же дерево можно представить так:

      20
    /   \
  10     30
 /  \    / \
5   15  25  40

А с троичными деревьями всё куда интересней :) Мы можем пытаться оптимизировать дерево по нескольким критериям (по размеру, например), если очень хочется. Но на скорости поиска это никак не скажется. Вот цитата из статьи Ternary Search Trees (Dr. Dobb's):

Better Insertion Orders

In what order should you insert the nodes into a tree? No matter in what order you insert the nodes, you end up with the same digital search trie -- the data structure is totally insensitive to insertion order. Binary search trees are at the opposite end of the spectrum: If you insert the nodes in a good order (middle element first), you end up with a balanced tree. If you insert the nodes in sorted order, the result is a long skinny tree that is very costly to build and search. Fortunately, if you insert the nodes in random order, a binary search tree is usually close to balanced.

Ternary search trees fall between these two extremes. You can build a completely balanced tree by inserting the median element of the input set, then recursively inserting all lesser elements and greater elements. A simpler approach first sorts the input set. The recursive build function inserts the middle string of its subarray, then recursively builds the left and right subarrays. We use this method in our experiments; it is fast and produces fairly well-balanced trees. The cost of inserting all words in a dictionary with function insert3 is never more than about 10 percent greater than searching for all words. D.D. Sleator and R.E. Tarjan describe theoretical balancing algorithms for ternary search trees in "Self-Adjusting Binary Search Trees" (Journal of the ACM, July 1985).

Про ++ не скажу, вот, вроде тут на C наглядно, с примерами кода для балансировки бинарных деревьев.

4
  • Интересно, а балансировка как в двоичном дереве (скажем, АВЛ) даст сбалансированное троичное? (в нем же, по сути, средний (по равенству) путь IMHO на скорость поиска вообще не влияет).
    – avp
    13 мая 2015 в 22:42
  • Да не особо должно влиять. Вот тут пишут, например: D.D. Sleator and R.E. Tarjan describe theoretical balancing algorithms for ternary search trees in "Self-Adjusting Binary Search Trees" (Journal of the ACM, July 1985). P.S. Развлекаюсь вот потихоньку :)
    – user6550
    13 мая 2015 в 23:22
  • Первая ссылка кривая оказалась, вот правильная: drdobbs.com/database/ternary-search-trees/184410528?pgno=2
    – user6550
    14 мая 2015 в 9:50
  • @klopp: Круто, я нигде не видел русскоязычных обсуждений троичного дерева.
    – VladD
    14 мая 2015 в 13:13

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.