Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску
Резьбовая дерево , со специальными пронизывающими ссылками , представленная пунктирными стрелками

В вычислении , A резьбовой бинарное дерево представляет собой бинарное дерево вариант , который облегчает обход в определенном порядке (часто тот же порядок уже определены для дерева).

По всему двоичному дереву сортировки можно легко пройти по основному ключу, но при наличии только указателя на узел поиск следующего узла может быть медленным или невозможным. Например, листовые узлы по определению не имеют потомков, поэтому ни один другой узел не может быть достигнут при наличии только указателя на листовой узел - конечно, который включает желаемый «следующий» узел. Многопоточное дерево добавляет дополнительную информацию в некоторые или все узлы, поэтому «следующий» узел может быть найден быстро. Его также можно пройти без рекурсии и без дополнительной памяти (пропорциональной глубине дерева), которая требуется.

Threading [ править ]

"Бинарное дерево распределяется по потокам , делая все правые дочерние указатели, которые обычно были бы нулевыми указателями на последовательного преемника узла ( если он существует), и все левые дочерние указатели, которые обычно были бы нулевыми указателями на упорядоченного предшественника. узла ". [1]

Предполагается, что порядок обхода такой же, как и при обходе дерева по порядку . Однако указатели можно вместо (или в дополнение) добавлять к узлам дерева, а не заменять. Определенные таким образом связанные списки также обычно называются «потоками» и могут использоваться для обеспечения возможности обхода в любом желаемом порядке (ах). Например, дерево, узлы которого представляют информацию о людях, может быть отсортировано по имени, но иметь дополнительные потоки, позволяющие быстро перемещаться по дате рождения, весу или любой другой известной характеристике.

Мотивация [ править ]

Деревья, включая (но не ограничиваясь) деревьями двоичного поиска , могут использоваться для хранения элементов в определенном порядке, например значения некоторого свойства, хранящегося в каждом узле, часто называемого ключом . Одна из полезных операций в таком дереве - обход : просмотр всех элементов в порядке ключа.

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

Алгоритм обхода ( t ):

  • Вход: указатель t на узел (или ноль )
  • Если t = nil , вернуть.
  • Еще:
    • траверс (левый ребенок ( т ))
    • Посетите t
    • траверс (правый ребенок ( т ))

Одна из проблем этого алгоритма заключается в том, что из-за его рекурсии он использует пространство стека, пропорциональное высоте дерева. Если дерево достаточно сбалансировано, это составляет O (log n ) пространства для дерева, содержащего n элементов. В худшем случае, когда дерево принимает форму цепочки , высота дерева равна n, поэтому алгоритм занимает O ( n ) пространство. Вторая проблема заключается в том, что все обходы должны начинаться с корня, если узлы имеют указатели только на своих дочерних узлов. Обычно имеется указатель на конкретный узел, но этого недостаточно для возврата к остальной части дерева, если не добавлена ​​дополнительная информация, например указатели потоков.

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

В учебнике 1968 года Дональд Кнут спросил, существует ли нерекурсивный алгоритм обхода по порядку, который не использует стек и оставляет дерево без изменений. [2] Одним из решений этой проблемы является распараллеливание дерева, представленное Дж. Х. Моррисом в 1979 году. [3] [4] В последующем издании 1969 года [5] Кнут приписал представление дерева с нитями Перлису и Торнтону (1960). ). [6]

Связь с родительскими указателями [ править ]

Другой способ достичь аналогичных целей - включить в каждый узел указатель на родительский узел этого узла. При этом «следующий» узел всегда доступен. "правильные" указатели по-прежнему равны нулю, если нет правильных дочерних элементов. Чтобы найти «следующий» узел от узла, правый указатель которого равен нулю, пройдите через «родительские» указатели до тех пор, пока не дойдете до узла, правый указатель которого не равен нулю и не является потомком, из которого вы только что вышли. Этот узел является «следующим» узлом, а после него идут его потомки справа.

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

Типы [ править ]

  1. Однопоточные: каждый узел имеет резьбу в направлении либо предшественника в заказе или преемник (слева или справа).
  2. Двухпотоковый: каждый узел направлен как на предшественника, так и на преемника в порядке (слева и справа).

В Python :

def  parent ( узел ):  если  узел  является  узлом . дерево . root :  return  None  else :  x  =  node  y  =  node  while  True :  if  is_thread ( y ):  p  =  y . правильно,  если  p  равно  None  или  p . left  не является  узлом : p = x, а не       is_thread ( стр . слева ):  p  =  p . слева  p  =  p . left  return  p  elif  is_thread ( x ):  p  =  x . влево,  если  p  равно  None  или  p . right  не является  узлом : p = y, а не is_thread ( p . right ): p = p .          справа  p  =  p . Правый  возврат  p  x  =  x . осталось  y  =  y . Правильно

Массив обхода по порядку [ править ]

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

В-порядка обход резьбового дерева A,B,C,D,E,F,G,H,I, предшественник EIS D, преемник Eявляется F.

ThreadTree Inorder Array.png

Пример [ править ]

ThreadTree Inorder Array123456789.png

Давайте сделаем многопоточное двоичное дерево из обычного двоичного дерева:

В заказе обход для вышеприведенного дерева - DBAE C. Таким образом, соответствующее Каскадные бинарное дерево будет -

Нулевые ссылки [ править ]

В многопоточном двоичном дереве с n узлами имеется n * m - (n-1) пустых ссылок.

Итерационный обход [ править ]

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

Обход по порядку по определению сначала посещает левое поддерево каждого узла (если оно существует и еще не посещалось); затем он посещает сам узел и, наконец, правое поддерево узла (если оно существует). Если правое поддерево не существует, но есть многопоточная ссылка, мы делаем резьбовой узел текущим рассматриваемым узлом. Пример показан ниже.

Алгоритм [ править ]

  1. Если у текущего узла есть левый дочерний элемент, которого нет в списке посещений, перейдите к шагу 2, иначе - к шагу 3.
  2. Поместите этот левый дочерний элемент в список посещенных узлов и сделайте его текущим узлом. Переходите к шагу 6.
  3. Посетите узел. Если у узла есть правильный дочерний элемент, переходите к шагу 4, иначе переходите к шагу 5.
  4. Сделайте правый дочерний элемент текущим узлом. Переходите к шагу 6.
  5. Если есть узел потока, сделайте его текущим узлом.
  6. Если все узлы напечатаны, то завершите, иначе переходите к шагу 1.
ШагЛи
1У «А» есть левый ребенок В, которого никто не посещал. Итак, мы помещаем B в наш список посещенных узлов, и B становится нашим текущим узлом.B
2У «B» есть левый дочерний элемент «D», которого нет в нашем списке посещенных узлов. Итак, мы помещаем «D» в этот список и делаем его нашим текущим узлом.BD
3У «D» нет левого потомка, поэтому мы посещаем «D». Затем мы проверяем его правого ребенка. «D» не имеет правого дочернего элемента, поэтому мы проверяем его ссылку на поток. У него есть поток, идущий до узла «B». Итак, мы делаем «B» текущим узлом.BDD
4У «B» есть левый дочерний элемент, но он уже находится в списке посещенных узлов. Итак, посетите «Б». Теперь проверьте, есть ли у него правильный ребенок. Это не. Итак, сделайте его резьбовой узел (то есть «A») текущим узлом.BDБД
5У «А» есть левый дочерний элемент «В», но он уже посещен. Итак, посетите «А». Теперь у «А» есть правильный дочерний элемент «С», и он не посещается. Так что добавьте его в список и сделайте текущим узлом.BDCDBA
6У «C» есть левый дочерний элемент «E», который не посещается. Добавьте его в список и сделайте текущим узлом.BDCEDBA
7и наконец.....DBAEC

Ссылки [ править ]

  1. ^ Ван Вик, Кристофер Дж. Структуры данных и программы на языке C , Аддисон-Уэсли, 1988, стр. 175. ISBN  978-0-201-16116-8 .
  2. ^ Knuth, DE (1968). Фундаментальные алгоритмы . Искусство программирования. 1 (1-е изд.). Чтение / MA: Эддисон Уэсли.
  3. ^ Моррис, Джозеф Х. (1979). «Простой и дешевый обход бинарных деревьев». Письма об обработке информации . 9 (5). DOI : 10.1016 / 0020-0190 (79) 90068-1 .
  4. ^ Матети, Прабхакер; Мангирмалани, Рави (1988). «Пересмотрен алгоритм обхода дерева Морриса». Наука компьютерного программирования . 11 : 29–43. DOI : 10.1016 / 0167-6423 (88) 90063-9 .
  5. ^ Knuth, DE (1969). Фундаментальные алгоритмы . Искусство программирования. 1 (2-е изд.). Эддисон Уэсли. Hre: Раздел 2.3.1 «Обход двоичных деревьев».
  6. ^ Перлис, Алан Джей; Торнтон, К. (апрель 1960 г.). «Манипуляция символами с помощью цепочек списков». Коммуникации ACM . 3 (4): 195–204. DOI : 10.1145 / 367177.367202 .

Внешние ссылки [ править ]

  • GNU libavl 2.0.2, Раздел о многопоточных деревьях двоичного поиска