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

Question

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

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

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

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

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

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

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

Answer 1

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

Формально:

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

РЕДАКТИРОВАТЬ : когда речь идет о концепции максимальной глубины, она идентична высоте дерева [которая максимальна у корня], вы можете доказать это по индукции.

Answer 5

Высота узла со ссылкой на Leaf - длина самого длинного пути к конечному узлу от исходного узла.

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

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

Answer 6

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

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

Answer 7

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

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

Answer 8

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;
}

Answer 9

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

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

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