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

Question

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

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

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

Answer 1

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

Возьмите это дерево, например:

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

Answer 2

Я не знаю ответа, но на основании описания в книге он звучит так ...

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

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

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

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

---

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

Answer 3

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

Answer 4

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

для дерева размера 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