Co to jest drzewo wyszukiwania?
Drzewo wyszukiwania to struktura danych wykorzystywana w programowaniu komputerowym do przechowywania i organizowania listy danych. Każde drzewo wyszukiwania składa się z uporządkowanego zestawu węzłów. Węzły te można połączyć z zero lub więcej innymi węzły. Poszczególne węzły zawierają pewne dane, a także łącza do innych węzłów. Dane zawarte w węzłach drzewa bardzo często są uporządkowane w jakiś sposób, aby umożliwić wyszukiwanie efektywnych algorytmów, z łatwością wstawiaj i usuwaj węzły.
Węzły drzewa wyszukiwania są opisane czterema ważnymi terminami. Wierzchołek drzewa, w którym znajduje się pierwszy węzeł, nazywany jest korzeniem. Jeśli węzeł zawiera łącza do podrzędnych -nodes, ten węzeł jest znany jako rodzic. Węzły poniżej rodzica są nazywane dziećmi, a każdy węzeł, który nie ma węzłów potomnych, nazywany jest liściem. węzeł główny został zidentyfikowany, ponieważ nie ma elementu nadrzędnego, a węzły liści nie będą miały elementów podrzędnych.
Program jest w stanie poruszać się po drzewie w poszukiwaniu danych, rozpoczynając od określonego węzła, wykonując kontrolę warunkową, a następnie przechodząc do następnego węzła logicznego, jeśli wymagane dane nie są obecne. W zależności od zastosowanej struktury danych , wyszukiwanie może zająć różną ilość czasu. Jeśli drzewo wyszukiwania jest zorganizowane podczas dodawania i usuwania węzłów, wyszukiwanie może być bardzo szybkie. Po złożeniu drzewa losowo, jest nieposortowane lub pozwala wielu rodzicom, wyszukiwanie może zająć bardzo dużo czasu.
Jednym z czynników wpływających na korzystanie z drzew wyszukiwania jest kwestia równowagi. Zrównoważone drzewo to takie, w którym zarówno prawy, jak i lewy element podrzędny węzła głównego zawierają taką samą głębokość węzłów podrzędnych lub mieszczą się w obrębie jednego Głębokość drzewa to liczba węzłów od najniższego liścia drzewa do korzenia. Niezrównoważone drzewo może mieć wszystkie węzły tylko z jednej strony lub mieć wszystkie węzły ułożone liniowo, bez rozgałęzień. Gdy głębokość drzewa rośnie, szybkość algorytmów wyszukiwania może się dramatycznie zmniejszyć.
Istnieją pewne typy drzew wyszukiwania, które są określane jako samowyważenie. Drzewa te używają operacji, takich jak obracanie drzew, aby pomóc zachować równowagę przy jednoczesnym zachowaniu kolejności danych w liściach. obroty drzewa mogą spowalniać program podczas dodawania i usuwania węzłów, przeciwdziała temu szybkość, z jaką dane mogą być pobierane.
Chociaż istnieje wiele rodzajów drzew wyszukiwania, najczęstszą strukturą drzewa danych jest drzewo wyszukiwania binarnego. Ten typ danych składa się z węzłów, z których każdy ma zero do dwóch węzłów potomnych. Istnieje tylko jeden węzeł główny, a wszystkie liście w drzewie są uporządkowane od lewej do prawej w rosnących wartościach zgodnie z przechowywanymi danymi. Istnieje wiele algorytmów dla drzew wyszukiwania binarnego, które mogą bardzo ułatwia zamawianie danych.
Nie ma jednej standardowej implementacji dla węzłów drzewa wyszukiwania. Węzły mogą być reprezentowane przez wiele różnych struktur danych. Można stosować tablice tablic, a także multiplikować połączone listy. Często drzewo wyszukiwania wykorzystuje niestandardową strukturę danych, która została zaprojektowana, aby pomóc w zakończeniu niezbędnych operacji wymaganych przez program Niektóre standardowe biblioteki programistyczne zawierają nawet własne wewnętrzne implementacje drzew wyszukiwania.