Jaka jest różnica między głębokością drzewa a wysokością?

262

To proste pytanie z teorii algorytmów.
Różnica między nimi polega na tym, że w jednym przypadku liczy się liczbę węzłów, a drugą liczbę krawędzi na najkrótszej ścieżce między węzłem głównym a węzłem betonowym.
Który jest który?

Gabriel Ščerbák
źródło
78
Wskazówka: aby uniknąć pomyłek między terminologiami: 1. Wysokość: wyobraź sobie, że mierząc wzrost osoby, wykonujemy ją od stóp do głów (od liścia do korzenia). 2. Głębokość: wyobraź sobie pomiar głębokości morza, robimy to od powierzchni ziemi do dna oceanu (od korzenia do liścia).
Yesh,
@Yesh To świetna analogia.
Postać specjalna
1
Aby dodać do doskonałej analogii @Yesh: dla jakiegoś wewnętrznego węzła pośrodku drzewa głębokością jest liczba poziomów poniżej węzła głównego, a wysokość to poziom powyżej jego najniższego węzła potomnego.
Thomas Nguyen

Odpowiedzi:

663

Dowiedziałem się, że głębokość i wysokość to właściwości węzła :

  • Głębokość węzła jest liczba krawędzi od węzła do węzła korzenia drzewa.
    Węzeł główny będzie miał głębokość 0.

  • Wysokość węzła jest liczba krawędzi na najdłuższej ścieżki od węzła do liścia.
    Węzeł liścia będzie miał wysokość 0.

Właściwości drzewa :

  • Wysokość drzewa byłaby wysokość jego korzenia,
    lub równoważnie, głębokość najgłębszej węzła.

  • Średnica (lub szerokość ) drzewa jest liczba węzłów na najdłuższej ścieżce między dwoma dowolnymi węzłami liści. Drzewo poniżej ma średnicę 6 węzłów.

Drzewo o wysokości i głębokości każdego węzła

Daniel AA Pelsmaeker
źródło
20
+1 miał właśnie dodać cytat o tej samej treści stąd: en.wikipedia.org/wiki/Tree_%28data_structure%29
Péter Török
2
oznacza to, że wysokość == maksymalna głębokość
roottraveller
6
@rkm_Hodor: Tak, wysokość drzewa jest zawsze równa głębokości najgłębszego węzła.
Daniel AA Pelsmaeker
1
Czy możesz przytoczyć źródło swojego twierdzenia, że ​​średnica drzewa liczy węzły zamiast krawędzi? Jest to sprzeczne ze zwykłą definicją średnicy wykresu (patrz np. En.wikipedia.org/wiki/Distance_(graph_theory) ), która pyta o najdłuższą ścieżkę.
j_random_hacker
1
@j_random_hacker To kwestia definicji, wybierz tę, która najbardziej Ci odpowiada. Aby przejść od liczby wierzchołków do liczby krawędzi, po prostu odejmij 1. Wolę policzyć liczbę wierzchołków, ponieważ daje to wykres z tylko jednym węzłem o szerokości 1 i pustym wykresem o szerokości 0. mathworld. wolfram.com/GraphDiameter.html
Daniel AA Pelsmaeker
44

wysokość i głębokość drzewa jest równa ...

ale wysokość i głębokość węzła nie jest równa, ponieważ ...

wysokość oblicza się, przechodząc od danego węzła do najgłębszego możliwego liścia.

głębokość jest obliczana na podstawie przejścia od korzenia do danego węzła .....

Praveen_Shukla
źródło
4
„wysokość jest obliczana przez przejście od liścia do danego węzła” nie jest poprawne, liść musi być tym, który jest najgłębszy spośród wszystkich liści danego węzła.
mightyWOZ
14

Według Cormen i in. Wprowadzenie do algorytmów (Załącznik B.5.3), głębokość węzła X w drzewie T jest zdefiniowana jako długość prostej ścieżki (liczba krawędzi) od węzła głównego T do X. Wysokość węzła Y wynosi liczba krawędzi na najdłuższej prostej ścieżce w dół od Y do liścia. Wysokość drzewa jest definiowana jako wysokość jego węzła głównego.

Zauważ, że prosta ścieżka to ścieżka bez powtarzalnych wierzchołków.

Wysokość drzewa jest równa maksymalnej głębokości drzewa . Głębokość węzła i wysokość węzła niekoniecznie są równe. Patrz rysunek B.6 trzeciej edycji Cormen i in. dla ilustracji tych pojęć.

Czasami widziałem problemy z proszeniem jednego o policzenie węzłów (wierzchołków) zamiast krawędzi, więc poproś o wyjaśnienie, jeśli nie jesteś pewien, czy powinieneś policzyć węzły lub krawędzie podczas egzaminu lub rozmowy kwalifikacyjnej.

lodowiec
źródło
Czy jest jakaś trudność w liczeniu węzłów i krawędzi. Wydaje się, że oba dają ten sam wynik. Popraw mnie, jeśli się mylę.
VINOTH ENERGETIC
@jdhao jak głębokość roota może wynosić 2? Jest to albo 0 (jeśli brane są pod uwagę krawędzie), albo 1 (jeśli brane są pod uwagę węzły).
neowulf33
@ neowulf33, tak, strasznie się mylę. Głębokość węzła głównego powinna wynosić 0. Usunę mój komentarz, aby nie mylić ludzi.
jdhao
2

Prosta odpowiedź:
Głębokość:
1. Drzewo : Liczba krawędzi / łuku od węzła głównego do węzła liścia drzewa nazywana jest głębokością drzewa.
2. Węzeł : Liczba krawędzi / łuku od węzła głównego do tego węzła jest nazywana głębokością tego węzła.

Akshay Sahu
źródło
2

Innym sposobem na zrozumienie tych koncepcji jest: Głębokość: Narysuj poziomą linię w pozycji pierwiastkowej i potraktuj tę linię jako grunt. Tak więc głębokość korzenia wynosi 0, a wszystkie jej elementy potomne rosną w dół, więc każdy poziom węzłów ma bieżącą głębokość + 1.

Wysokość: ta sama linia pozioma, ale tym razem pozycją ziemi są zewnętrzne węzły, które są liściem drzewa i liczą w górę.

Wilson Zhang
źródło
2

Chciałem napisać ten post, ponieważ jestem studentem studiów licencjackich i coraz częściej korzystamy z OpenDSA i innych podręczników typu open source. Wydaje się, że z najwyżej ocenianej odpowiedzi, że sposób uczenia się wysokości i głębokości zmienił się z pokolenia na pokolenie, i zamieszczam to, więc wszyscy są świadomi, że ta rozbieżność istnieje teraz i mam nadzieję, że nie spowoduje żadnych błędów programy! Dzięki.

Z książki OpenDSA Data Structures & Algos :

Jeśli n 1 , n 2 , ..., n k jest taką sekwencją węzłów w drzewie, że n i jest rodzicem n i +1 dla 1 <= i <k, to sekwencja ta nazywana jest ścieżką od n Od 1 do n k . Długość ścieżki wynosi k-1. Jeśli istnieje ścieżka od węzła R do węzła M, wówczas R jest przodkiem M, a M jest potomkiem R. Tak więc wszystkie węzły w drzewie są potomkami katalogu głównego drzewa, podczas gdy katalog główny jest przodkiem wszystkich węzłów. Głębokość węzła M w drzewie to długość ścieżki od korzenia drzewa do M. Wysokość drzewa jest o jeden większa niż głębokość najgłębszego węzła w drzewie.Wszystkie węzły głębokości d znajdują się na poziomie d w drzewie. Rdzeń jest jedynym węzłem na poziomie 0, a jego głębokość wynosi 0.

Rysunek 7.2.1

Rysunek 7.2.1: Drzewo binarne. Węzeł A jest korzeniem. Węzły B i C są dziećmi A. Węzły B i D razem tworzą poddrzewo. Węzeł B ma dwoje dzieci: jego lewe dziecko jest pustym drzewem, a prawe dziecko D. D. Węzły A, C i E są przodkami G. Węzły D, E i F tworzą 2 poziom drzewa; węzeł A znajduje się na poziomie 0. Krawędzie od A do C do E do G tworzą ścieżkę o długości 3. Węzły D, G, H i I są liśćmi. Węzły A, B, C, E i F są węzłami wewnętrznymi. Głębokość I wynosi 3. Wysokość tego drzewa wynosi 4.

jesion
źródło
Dla tego, co jest warte, zmieniono definicję tego łącza na: „Głębokość węzła M w drzewie to długość ścieżki od korzenia drzewa do M. Wysokość drzewa to głębokość najgłębszy węzeł w drzewie. ”
kaya3