Różnica między drzewkiem B i drzewem binarnym
Zawartość
- Wykres porównania
- Definicja B-drzewa
- Właściwości B-drzewa rzędu M
- Definicja drzewa binarnego
- Techniki przejścia
- Wniosek
Drzewo B i Drzewo binarne to typy nieliniowej struktury danych. Chociaż warunki wydają się podobne, ale różnią się we wszystkich aspektach. Drzewo binarne jest używane, gdy rekordy lub dane są przechowywane w pamięci RAM zamiast na dysku, ponieważ prędkość dostępu do pamięci RAM jest znacznie wyższa niż na dysku. Z drugiej strony, B-drzewo jest używane, gdy dane są przechowywane na dysku, co skraca czas dostępu poprzez zmniejszenie wysokości drzewa i zwiększenie gałęzi w węźle.
Inna różnica między drzewem B i drzewem binarnym polega na tym, że drzewo B musi mieć wszystkie swoje węzły podrzędne na tym samym poziomie, podczas gdy drzewo binarne nie ma takiego ograniczenia. Drzewo binarne może mieć maksymalnie 2 poddrzewa lub węzły, podczas gdy w drzewie B może mieć M liczbę poddrzewa lub węzłów, gdzie M jest rzędem drzewa B.
- Wykres porównania
- Definicja
- Kluczowe różnice
- Wniosek
Wykres porównania
| Podstawa do porównania | B-drzewo | Drzewo binarne |
|---|---|---|
| Zasadnicze ograniczenie | Węzeł może mieć maksymalnie M liczby węzłów potomnych (gdzie M jest rzędem drzewa). | Węzeł może mieć maksymalnie 2 liczby poddrzewa. |
| Używany | Służy do przechowywania danych na dysku. | Jest używany, gdy rekordy i dane są przechowywane w pamięci RAM. |
| Wysokość drzewa | logM. N (gdzie m jest rzędem drzewa M-way) | log2 N. |
| Podanie | Struktura danych indeksująca kod w wielu DBMS. | Optymalizacja kodu, kodowanie Huffmana itp. |
Definicja B-drzewa
Drzewo B to zrównoważone drzewo M-way, znane również jako zrównoważone drzewo sortowania. Jest podobny do drzewa wyszukiwania binarnego, w którym węzły są zorganizowane na podstawie wewnętrznego przemierzania. Złożoność przestrzenna B-drzewa wynosi O (n). Złożoność czasu wstawiania i usuwania wynosi O (log n).
Istnieją pewne warunki, które muszą być spełnione dla B-drzewa:
- Wysokość drzewa musi leżeć jak najmniej.
- Nad liśćmi drzewa nie powinno być pustych poddrzew.
- Liście drzewa muszą znajdować się na tym samym poziomie.
- Wszystkie węzły powinny mieć najmniejszą liczbę dzieci oprócz węzłów opuszczających.
Właściwości B-drzewa rzędu M
- Każdy węzeł może mieć maksymalną liczbę M dzieci i minimalną liczbę M / 2 dzieci lub dowolną liczbę od 2 do maksimum.
- Każdy węzeł ma jeden klucz mniej niż dzieci z maksymalną liczbą kluczy M-1.
- Rozmieszczenie kluczy jest w określonej kolejności w obrębie węzłów. Wszystkie klucze w poddrzewie znajdujące się po lewej stronie klucza są poprzednikami klucza, a te znajdujące się po prawej stronie klucza nazywane są następcami.
- W momencie wstawienia pełnego węzła drzewo dzieli się na dwie części, a klucz o wartości mediany jest wstawiany w węźle nadrzędnym.
- Scalanie odbywa się po usunięciu węzłów.
Definicja drzewa binarnego
Drzewo binarne to struktura drzewa, która może mieć maksymalnie dwa wskaźniki dla swoich węzłów podrzędnych. Oznacza to, że najwyższy stopień, jaki węzeł może mieć, to 2, a może także istnieć węzeł zero lub jeden stopień.
Istnieją pewne warianty drzewa binarnego, takie jak drzewo ściśle binarne, pełne drzewo binarne, rozszerzone drzewo binarne itp.
- Ściśle binarne drzewo jest drzewem, w którym każdy nieterminalny węzeł musi mieć lewe poddrzewo i prawe poddrzewo.
- Drzewo nazywane jest kompletnym drzewem binarnym, gdy spełnia warunek posiadania 2 ja węzły na każdym poziomie, gdzie i to poziom.
- Gwintowany plik binarny to drzewo binarne, które składa się z 0 liczby węzłów lub 2 liczby węzłów.
Techniki przejścia
Przechodzenie przez drzewa jest jedną z najczęstszych operacji wykonywanych na strukturze danych drzewa, w której każdy węzeł odwiedzał dokładnie raz w systematyczny sposób.
- Inorder - W tym przejściu drzewa lewe poddrzewo jest odwiedzane rekurencyjnie, następnie odwiedzany jest węzeł główny, aw ostatnim prawym poddrzewie odwiedzane.
- Preorer - W tym przejściu do drzewa węzeł główny jest odwiedzany najpierw, a następnie lewe poddrzewo, a na końcu prawe poddrzewo.
- Postorder - Ta technika odwiedza lewe poddrzewo, następnie prawe poddrzewo i wreszcie węzeł główny.
- W drzewie B maksymalna liczba węzłów potomnych, które może mieć nieterminalny węzeł, to M, gdzie M to kolejność B-drzewa. Z drugiej strony drzewo binarne może mieć najwyżej dwa poddrzewa lub węzły podrzędne.
- B-drzewo jest używane, gdy dane są przechowywane na dysku, natomiast drzewo binarne jest używane, gdy dane są przechowywane w szybkiej pamięci, takiej jak RAM.
- Innym obszarem zastosowania B-drzewa jest struktura danych indeksująca kod w DBMS, natomiast drzewo binarne jest wykorzystywane do optymalizacji kodu, kodowania huffmana itp.
- Maksymalna wysokość B-drzewa to logM.N (M jest rzędem drzewa). Przeciwnie, maksymalna wysokość drzewa binarnego to log2N (N to liczba węzłów, a podstawa to 2, ponieważ jest to wartość binarna).
Wniosek
B-drzewo jest używane przez binarne i binarne drzewo wyszukiwania, głównym powodem jest hierarchia pamięci, w której procesor jest podłączony do pamięci podręcznej z kanałami o wysokiej przepustowości, podczas gdy procesor jest podłączony do dysku przez kanał o niskiej przepustowości. Drzewo binarne jest używane, gdy rekordy są przechowywane w pamięci RAM (małe i szybkie), a drzewo B jest używane, gdy rekordy są przechowywane na dysku (duże i wolne). Zatem użycie drzewa B zamiast drzewa binarnego znacznie skraca czas dostępu z powodu wysokiego współczynnika rozgałęzienia i zmniejszonej wysokości drzewa.
