Junior
Czym jest drzewo binarne?
sobes.tech AI
Odpowiedź od AI
Drzewo binarne to struktura danych w kształcie drzewa, w której każdy węzeł ma nie więcej niż dwóch potomków: lewego i prawego.
Główne właściwości:
- Korzeń (Root): Najwyższy węzeł drzewa.
- Węzeł (Node): Element drzewa zawierający dane i odnośniki do jego potomków.
- Potomek (Child): Węzeł znajdujący się bezpośrednio pod innym węzłem (rodzicem).
- Rodzic (Parent): Węzeł, który ma bezpośrednio pod sobą jednego lub więcej potomków.
- Liść (Leaf): Węzeł nieposiadający potomków.
- Gałąź (Branch): Ścieżka od korzenia do liścia.
- Poddrzewo (Subtree): Drzewo składające się z węzła i wszystkich jego potomków.
Różne rodzaje drzew binarnych:
- Pełne drzewo binarne (Full Binary Tree): Każdy węzeł ma albo 0, albo 2 potomków.
- Idealnie zbalansowane drzewo binarne (Perfect Binary Tree): Wszystkie poziomy, oprócz ostatniego, są w pełni wypełnione, a na ostatnim poziomie wszystkie węzły są ułożone jak najbliżej lewej strony.
- Zbalansowane drzewo binarne (Balanced Binary Tree): Wysokość lewego i prawego poddrzewa dowolnego węzła różni się nie więcej niż o 1. Przykład: drzewo AVL, drzewo czerwono-czarne.
- Zdegenerowane drzewo binarne (Degenerate Binary Tree): Każdy węzeł ma nie więcej niż jednego potomka. W istocie jest to lista powiązana.
Stosowane w różnych algorytmach i strukturach danych, takich jak drzewa wyszukiwania binarnego, kopce, drzewa składniowe.