Глубина vs Высота дерева. Обновление основных принципов

Я занимаюсь обновлением алгоритмов и структур данных.

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

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

Таким образом, глубина корня (который является узлом) равна 0. Высота корня (или любого поднода) - максимальная высота его детей.

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

Например, в этом сообщении Проверьте, сбалансировано ли дерево, ответы фокусируются на высоте дерева, тогда как определение баланса может быть на глубине дерева

Правильно ли я понимаю, или я исповедую эти основы?

Ответы

Ответ 1

Говоря о дереве, они означают одно и то же: длина самого длинного пути от корня до листового узла.

Ответ 2

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

  • Корневой узел имеет глубину нуля
  • Узел X имеет глубину N
  • Высота дерева M

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

Ответ 3

глубина - это "насколько глубокий узел" [или как далеко это от корня]. высота - "насколько высока дерево" [или, насколько далеко от нее самый длинный лист)

Формально:

height(v) = 0                                                              v is a leaf
            max{height(u)|for every u such that u is a son of v} + 1       else

depth(v) = 0                                                                v root
           depth(u) + 1    where u is the parent of v                       else

EDIT: когда вы ссылаетесь на концепцию максимальной глубины, она идентична высоте дерева [, которая максимальна в корне], вы можете доказать это путем индукции.

Ответ 4

Высота узла - это длина самого длинного нисходящего пути к листу от этого узла. Высота корня - высота дерева.

Глубина узла - это длина пути к его корню (т.е. Его корневой путь). Это обычно необходимо при манипулировании различными деревьями с самобалансировкой, в частности, деревьями AVL. Корневой узел имеет нулевую глубину, у листовых узлов высота равна нулю, а дерево с единственным узлом (отсюда и корень и лист) имеет глубину и высоту ноль. Обычно пустое дерево (дерево без узлов, если таковые разрешены) имеет глубину и высоту -1.

Ответ 5

Высота дерева - это количество узлов от корня до листа, следующего за самым длинным путем. Итак, если у нас есть один узел (сам корень) height = 1 Пустое дерево: 0

Глубина или уровень любого узла - это количество ребер от корневого узла до этого узла. так что.. корень корня равен 0.

Таким образом, максимальная глубина дерева меньше высоты дерева.

Ответ 6

private static int getHeight(BTreeNode n){

    if(n == null)
        return 0;

    int lHeight = getHeight(n.left);
    int rheight = getHeight(n.right);

    int height = 1+Math.max(lHeight,rheight);

    return height;
}

Ответ 7

Глубина узла: длина пути от корня до узла. Высота узла: длина пути от узла до самого внутреннего узла (листа).

Но высота и глубина в случае дерева одинаковы. Высота дерева = Глубина дерева = Максимальная высота = Максимальная глубина.

Ответ 8

В дереве двоичного поиска

  1. Высота узла: # ребра на самом длинном простом нисходящем пути от узла до листа
  2. Высота дерева: высота корня
  3. Глубина узла: длина простого пути (# ребра) от корня до узла

Ответ 9

Высота узла относится к Листу - длина самого длинного пути к листовому узлу от исходного узла.

Глубина узла относится к корневому узлу. - общая длина от исходного узла до корневого

Но когда вы говорите вообще о целом дереве, то и другое относится к тому же, оно отличается только тем, что вы берете определенный узел внутри дерева