Путаница в терминологии при определении сбалансированного двоичного дерева: высота поддерева против высоты узла

Question

Ссылка на ответ на этот вопрос

Сбалансированное бинарное дерево:

1. Высота левого и правого поддеревьев различается не более чем на единицу, И
2. Левое поддерево сбалансировано, И
3. Правильное поддерево сбалансировано

Теперь, используя тот же пример

     A
   /   \
  B     C  
 /     / \  
D     E   F  
     /  
    G  

Дерево укоренено в A.

Теперь, глядя на определение сбалансированного по высоте дерева, первая точка говорит:

1. Высота левого и правого поддеревьев отличается не более чем на один

   Если я в данный момент нахожусь в узле A, чтобы определить высоту ЛЕВОГО поддерева A, я запутаюсь, если вычислю:

   • Высота узла A, смотрящего на самого глубокого левого ребенка из A (D) ИЛИ
   • Высота узла B, смотрящего на самого глубокого левого ребенка от A (по расширению B) (D)

   Если я в данный момент нахожусь в узле A, чтобы определить высоту ПРАВОГО ПОДВОДНОГО дерева A, я запутаюсь, если вычислю:

   • Высота узла A, смотрящего на самого глубокого правого потомка от A (F) ИЛИ
   • Высота узла C, смотрящего на самого глубокого правого потомка от A (по расширению C) (F)

Answer 1

«Высота поддерева» обычно переводится как «высота корня поддерева». Наткнулся на это объяснение, слушая эту MIT OpenCourseWare лекцию , в отметке времени 13: 17.