Лево сбалансированные бинарные деревья

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

Мне это показалось немного расплывчатым. Означает ли это, что листья находятся только с левой стороны корня и распределены по всему уровню, или листья существуют только с левой стороны всего дерева. Что именно представляют собой левые уравновешенные?

Я не уверен, покрывает ли моя догадка хоть какой-то ответ, поэтому, если бы кто-нибудь мог помочь, я был бы очень признателен :-).


binary-tree tree-balancing
person rubixibuc    schedule 01.09.2011    source источник

Ответы (4)


arrow_upward
6
arrow_downward

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

Возьмем, к примеру, это дерево:

введите описание изображения здесь

Это дерево сбалансировано, но не сбалансировано слева. Однако, если бы узел 67 был удален, дерево было бы сбалансированным по левому краю.

person Brandon E Taylor    schedule 01.09.2011
comment
Если бы 67 был левым ребенком из 54, оставался бы он сбалансированным? А что, если у 23-х есть правильный ребенок? - person rubixibuc; 02.09.2011
comment
Нет, потому что узел 23 находится «левее», чем узел 54, и поэтому должен быть «заполнен» первым. 67 должен быть правым ребенком из 23 лет, чтобы поддерживать его левое равновесие. - person Brandon E Taylor; 02.09.2011

arrow_upward
3
arrow_downward

Мне кажется, что определение левого сбалансированного двоичного дерева аналогично полному двоичному дереву.

person Simone    schedule 01.09.2011

arrow_upward
3
arrow_downward

Я действительно не знаю ответа, но, судя по описанию в книге, мне кажется, что это так ...

Для начала давайте подумаем об этом так. Каждая «строка» в дереве имеет номер, начиная с нуля и заканчивая обратным отсчетом. Строка с наибольшим номером считается последним уровнем.

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

          50
       /     \
     /         \
    35         70
   /  \       /  \
 10    34    57  90
 /     /        /
9     7        78

Если бы мы добавили «98» в качестве правого дочернего элемента для 90 или «59» в качестве правого дочернего элемента для 57, тогда это дерево больше не было бы сбалансированным по левому краю.

Изменить: прочитав ответ Брэндона Э. Тейлора, вам определенно не следует выбирать этот. После просмотра и повторного прочтения описания он не только становится более понятным, но и гораздо лучше соответствует описанию.

person user265312    schedule 01.09.2011

arrow_upward
1
arrow_downward

В дополнение к ответу Брэндона Э. Тейлора левое сбалансированное двоичное дерево - это двоичное дерево, которое при представлении в массиве не должно: t существуют какие-либо промежутки между элементами, представляющими узлы дерева.

например, для дерева размером 6, вот несколько возможных представлений массива со следующими критериями

1- let _ denote an empty slot in the array
2- let i be the index of a slot in an array (i is 1-based)
2- for any parent at index i the left child is at index (2*i) and the right child is at index (2*i)+1

1 2 3 4 _ _ <-  left balanced 
6 3 2 4 1   <-  left balanced
4 2 1 _ 6   <- not left balanced

чтобы уточнить детали, давайте представим ответ user265312:

50 35 70 10 34 57 90 9 _ 7 _ _ _ 78 _ <- not left balanced

между тем ответ Брэндона (после удаления узла 67) не нарушает правило левой балансировки:

50 17 72 12 23 54 76 9 14 19 _ _ _ _ _ <- left balanced
person A. Khaled    schedule 10.05.2019