Wprowadzenie do drzew w strukturze danych
Zanim zrozumiemy typy drzew w strukturze danych, najpierw zbadamy drzewa w strukturze danych. Drzewo w polu komputerowym jest również nazywane drzewem świata rzeczywistego, jednak różnica między światem rzeczywistym a drzewem pola obliczeniowego polega na tym, że jest on wizualizowany jako odwrócony do góry nogami i umieszczony na nim korzeń oraz gałąź od korzenia do liści drzewa. Wśród różnych rzeczywistych aplikacji wykorzystywana jest struktura danych drzewa, która może wykazać związki między różnymi węzłami z hierarchią nadrzędny-podrzędny. Z tego powodu jest również nazywany hierarchiczną strukturą danych. Jest najbardziej popularny w celu uproszczenia i przyspieszenia wyszukiwania i sortowania. Jest uważany za jedną z najsilniejszych i najbardziej zaawansowanych struktur danych. Drzewo jest reprezentacją nieliniowej struktury danych. Drzewo może być pokazane przy użyciu różnych typów danych zdefiniowanych przez użytkownika lub pierwotnych. Możemy użyć tablic, klas powiązanych list lub innych rodzajów struktur danych do implementacji drzewa. Jest to grupa powiązanych ze sobą węzłów. Węzły są przymocowane do krawędzi, aby pokazać związek.
Relacje w drzewie: Na powyższym diagramie P jest korzeniem drzewa, również P jest rodzicem Q, R i S. Q jest dzieckiem P. Stąd Q, R i S są rodzeństwem. Podczas gdy P jest dziadkiem A, B, C, D i E.
Co to są drzewa?
Drzewo to hierarchiczna struktura danych, która naturalnie przechowuje informacje w sposób hierarchiczny. Struktura danych drzewa jest jedną z najbardziej wydajnych i dojrzałych. Węzły połączone krawędziami są reprezentowane.
Właściwości drzewa: Każde drzewo ma określony węzeł główny. Każdy węzeł drzewa może być skrzyżowany z węzłem głównym. Nazywa się to root, ponieważ drzewo było jedynym rootem. Każde dziecko ma tylko jednego rodzica, ale rodzic może mieć wiele dzieci.
Rodzaje drzew w strukturze danych
Poniżej znajdują się rodzaje drzew w strukturze danych:
1. Ogólne drzewo
Jeśli w hierarchii drzewa nie ma żadnych ograniczeń, drzewo jest nazywane drzewem ogólnym. Każdy węzeł może mieć nieskończoną liczbę dzieci w General Tree. Drzewo jest super zestawem wszystkich innych drzew.
2. Drzewo binarne
Drzewo binarne jest rodzajem drzewa, w którym można znaleźć większość dwojga dzieci dla każdego rodzica. Dzieci są znane jako lewe dziecko i prawe dziecko. Jest to bardziej popularne niż większość innych drzew. Kiedy pewne ograniczenia i cechy są stosowane w drzewie binarnym, stosuje się również wiele innych, takich jak drzewo AVL, BST (drzewo wyszukiwania binarnego), drzewo RBT itp. Kiedy przejdziemy do przodu, szczegółowo wyjaśnimy wszystkie te style.
3. Drzewo wyszukiwania binarnego
Binary Search Tree (BST) to rozszerzenie drzewa binarnego z kilkoma opcjonalnymi ograniczeniami. Lewa wartość podrzędna węzła powinna być w BST mniejsza lub równa wartości nadrzędnej, a prawa wartość podrzędna zawsze powinna być większa lub równa wartości nadrzędnej. Ta właściwość Binarnego drzewa wyszukiwania czyni go idealnym do operacji wyszukiwania, ponieważ możemy dokładnie określić w każdym węźle, czy wartość znajduje się w lewym, czy w prawym poddrzewie. Właśnie dlatego nazywa się Drzewo wyszukiwania.
4. Drzewo AVL
Drzewo AVL jest samo-równoważącym się drzewem wyszukiwania binarnego. W imieniu wynalazców Adelson-Velshi i Landis podano nazwę AVL. To było pierwsze drzewo, które balansowało dynamicznie. Współczynnik równoważący jest przydzielany dla każdego węzła w drzewie AVL na podstawie tego, czy drzewo jest zrównoważone, czy nie. Wysokość węzłów dzieci wynosi co najwyżej 1. AVL winorośli. W drzewie AVL poprawnym współczynnikiem równowagi jest 1, 0 i -1. Jeśli drzewo ma nowy węzeł, zostanie obrócony, aby zapewnić równowagę drzewa. Następnie zostanie obrócony. Typowe operacje, takie jak przeglądanie, wstawianie i usuwanie, zajmują czas O (log n) w drzewie AVL. Najczęściej stosuje się go podczas pracy z operacjami wyszukiwania.
5. Czerwono-czarne drzewo
Innym rodzajem drzewa automatycznego równoważenia jest czerwono-czarny. Podano czerwono-czarną nazwę, ponieważ czerwono-czarne drzewo ma czerwony lub czarny kolor na każdym węźle, zgodnie z właściwościami czerwono-czarnego drzewa. Utrzymuje równowagę lasu. Chociaż to drzewo nie jest drzewem w pełni zrównoważonym, operacja wyszukiwania zajmuje tylko czas O (log n). Gdy nowe węzły zostaną dodane do Czerwono-czarnego drzewa, wówczas węzły zostaną ponownie obrócone, aby zachować właściwości Czerwono-czarnego drzewa.
6. Drzewo N-ary
Maksymalna liczba dzieci w tym typie drzewa, które mogą mieć węzeł, to N. Drzewo binarne to drzewo dwuletnie, co najwyżej 2 dzieci w każdym węźle drzewa binarnego. Kompletne drzewo N-ary to drzewo, w którym dzieci węzła mają 0 lub N.
Zalety drzewa
Teraz zrozumiemy zalety drzewa:
- Drzewo odzwierciedla połączenia strukturalne danych.
- Drzewo służy do hierarchii.
- Oferuje wydajną procedurę wyszukiwania i wstawiania.
- Drzewa są elastyczne. Pozwala to na przeniesienie poddrzewa przy minimalnym wysiłku.
Wniosek - rodzaje drzew w strukturze danych
Więc w tym artykule widzieliśmy, co to jest struktura drzewa, jakie są różne typy drzew w strukturze danych i jakie są korzyści. Mam nadzieję, że masz pojęcie o niektórych typowych drzewach w strukturze danych.
Polecane artykuły
Jest to przewodnik po typach drzew w strukturze danych. Tutaj omawiamy, czym są drzewa, 6 rodzajów drzew w strukturze danych, z zaletami. Możesz również przejrzeć nasze inne powiązane artykuły, aby dowiedzieć się więcej -
- Potok danych AWS
- Oracle Data Warehousing
- Wielowymiarowa baza danych
- Struktura danych Pytania do wywiadu Java