Различные интерпретации высоты бинарного дерева

Question

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

Высота бинарного дерева, так как он также используется в AVL дерева поиска.

Согласно книге, я следую «ДАННЫМ СТРУКТУРАм от Lipschutz», в ней говорится: «глубина (или высота) дерева T - максимальное количество узлов в ветви T. Это оказывается еще 1 чем наибольшее количество T. Дерево 7 на рисунке 7.1 имеет глубину 5. "

цифра 7,1:

   A 
      /\ 
     / \   
     / \ 
     /  \ 
     B   C 
    /\  /\ 
     D E  G H 
     /  /\ 
     F   J K 
       /
       L 

Но, по ряду других ресурсов, высота была рассчитана по-разному, хотя такое же определение дается. Например, как я читал из интернета http://www.cs.utexas.edu/users/djimenez/utsa/cs3343/lecture5.html

"Вот пример бинарного дерева:.

    1 
       /\ 
       / \ 
       / \ 
      /  \ 
       2   3 
      /\  /\ 
      / \ / \ 
     / \ / \ 
      6  7 4  5 
     /\ /  /
     9 10 11  8 

Высота дерева максимум глубины всех узлов Таким образом, выше дерево имеет высота 3. «

Другой источник http://www.comp.dit.ie/rlawlor/Alg_DS/searching/3.%20%20Binary%20Search%20Tree%20-%20Height.pdf

говорит,» высота бинарного дерева для дерева с только один узел, корневой узел, высота определяется как 0, если есть 2 уровней узлов высота равна 1 и так далее. Нулевое дерево (без узлов, за исключением нулевого узла) определяется как высота -1. «

Теперь эти последние 2 объяснения соответствуют друг другу, но не с примером, приведенным в книге.

Другой источник говорит:» ​​Есть два соглашения, чтобы определить высоту Binary Tree 1) Количество узлов на самый длинный путь от корня до самого глубокого узла. 2) Количество ребер на самом длинном пути от корня до самого глубокого узла.

В этом посте следует первое соглашение. Например, высота ниже дерева 3.

   1 
      /\ 
      2 3 
     /\ 
      4 5 

" В этом, я хочу спросить, как может количество узлов и ребер между корнем и листом быть то же самое? А что будет высота из листового узла, согласно книге, оно должно быть 1 (так как число наибольшего уровня равно 0, поэтому высота должна быть 0 + 1 = 1, , но обычно говорят, что высота листового узла равна 0. Также почему в книге упоминаются глубина и высота, как одна и та же вещь? Эта вещь действительно меня сбивает с толку, я попытался уточнить из нескольких источников, но не могу выбрать между двумя интерпретациями. Пожалуйста, помогите.

==> Я хотел бы добавить к нему с тех пор, как я принимаю условные обозначения книги в теме деревьев поиска AVL, где нам нужно вычислить БАЛАНСНЫЙ ФАКТОР (в чем разница высот слева и правые поддерева) он говорит:

  C (-1) 
     /\ 
     (0) A G (1) 
      /
      D (0) 

число в скобках являются факторами баланса.

Теперь, если я должен следовать за книгой, высота D равна 1, а правое поддерево G имеет высоту (-1) с ее пустым, поэтому коэффициент Баланса G должен быть = 1 - (- 1) = 2!

Теперь, почему он взял высоту D, чтобы быть здесь 0?

ПОЖАЛУЙСТА, ПОМОГАЙТЕСЬ.

Answer 1

Точное определение высоты не имеет значения, если вы заботитесь о балансе. Напомним, что фактор баланс

height(left) - height(right) 

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

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

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