Dwie definicje zrównoważonych drzew binarnych

26

Widziałem dwie definicje zrównoważonych drzew binarnych, które wyglądają inaczej dla mnie.

  1. Drzewo binarne jest zrównoważone, jeśli dla każdego węzła utrzymuje, że liczba wewnętrznych węzłów w lewym poddrzewie i liczba wewnętrznych węzłów w prawym poddrzewie różnią się co najwyżej o 1.

  2. Drzewo binarne jest zrównoważone, jeśli dla dowolnych dwóch liści różnica głębokości wynosi co najwyżej 1.

Czy każde drzewo, które spełnia def. 1 również spełniają def. 2? Co na odwrót?

forrestGump
źródło
2
Czy próbowałeś udowodnić jeden z tych kierunków? Jakie są twoje ustalenia?
Raphael

Odpowiedzi:

17

Definicja 1. jest również znana jako równoważenie ciężaru ¹, a definicja 2. jako równoważenie wzrostu .

Wyważenie wysokości nie oznacza wyważenia ciężaru; przykładami są zarówno drzewa AVL, jak i drzewa czerwono-czarne. Zobacz tutaj i tutaj, aby uzyskać dowody, odpowiednio.

Równowaga masy oznacza jednak wyważenie wysokości. Można to udowodnić, pokazując następujący silniejszy fakt przez indukcję (ponad wzrost): zrównoważone pod względem masy drzewo jest kompletne na wszystkich poziomach, ale najgłębszych². Zasadniczym argumentem na etapie indukcyjnym jest to, że poddrzewa nie mogą mieć różnicy wysokości większej niż jeden, ponieważ - obie posiadające deklarowaną właściwość poprzez hipotezę indukcyjną - nie byłyby wtedy równoważone wagowo.


  1. Artykuł podaje inną, bardziej ogólną definicję.
  2. kkk-1
Raphael
źródło
Właśnie zdałem sobie sprawę, że silniejszy fakt może być wykorzystany do marnotrawstwa uproszczenia dowodów, które łączę.
Raphael
Być może dobrym pomysłem jest włączenie tej realizacji do swojej odpowiedzi.
Dyskretna jaszczurka
@Discretelizard Masz na myśli inne odpowiedzi?
Raphael
Och, nie zdawałem sobie sprawy, że te linki były odpowiedziami na informatykę lub że były twoimi odpowiedziami. W każdym razie chciałem tylko powiedzieć, że dobrym pomysłem może być spisanie uproszczonych dowodów. Twoje połączone odpowiedzi wydają się być odpowiednim miejscem.
Dyskretna jaszczurka