Co to jest drzewo binarne?

Drzewo binarne to rodzaj struktury danych używanej w programowaniu komputerowym do przechowywania, sortowania i dostępu do informacji.Drzewa binarne są najprostszą różnorodnością drzewa, ale są bardzo przydatne i łatwe do wdrożenia.Typowa implementacja drzewa binarnego opiera się na węźle głównym połączonym z serią węzłów, które tworzą sam drzewo przez zmienne wskaźnika.Ten rodzaj drzewa wywodzi swoją nazwę z faktu, że żaden węzeł w drzewie nie może mieć więcej niż dwoje dzieci.

Struktury danych drzewa występują w wielu odmianach.Składają się z różnych węzłów, które są zorganizowane w hierarchicznym wzorze.Jeden węzeł, root, jest punktem dostępu, za pomocą którego można przeszukać całe drzewo danych lub w inny sposób manipulować.Ten węzeł główny wskazuje górny węzeł w samym drzewie.

Każdy węzeł w drzewie, z wyjątkiem najwyższego węzła, będzie miał węzeł nadrzędny, który znajduje się nad nim w hierarchii drzewa.Może również mieć węzły dziecięce, które znajdują się poniżej.Dostęp do danego węzła jest dostępny przez te powyżej w drzewie i zapewnia dostęp do osób poniżej.Dany węzeł może zatem mieć do niego zero, jeden lub dwoje węzłów dzieci.Zwykłe drzewa binarne zezwalają na węzły z dowolną liczbą dzieci w dowolnym momencie drzewa.Nie kładą również żadnych ograniczeń dotyczących tego, w jaki sposób wartości przechowywane w węzłach zawierających drzewo.

Struktury danych są najbardziej przydatne, gdy poprawiają prędkość, z jaką można uzyskać dostęp do komputera, a do zmodyfikowanych wersji drzew binarnychpoprawić ich wydajność.Drzewo wyszukiwania binarnego jest takie, w którym wszystkie wartości danych znajdują się na lewym malejącej gałęzi z danego węzła, mają wartości równe lub mniej niż wartość przechowywana w tym węźle.Wartości po prawej stronie węzła w uporządkowanym drzewie binarnym muszą z kolei być większe niż wartość w węźle podstawowym.Zamawianie danych pozwala na napisanie znacznie bardziej wydajnego algorytmu wyszukiwania.

Kształt drzewa binarnego jest również ważny przy określaniu wydajności algorytmu wyszukiwania.Najmniej wydajna różnorodność drzewa binarnego jest taka, w której każdy węzeł ma tylko jedno dziecko.Komputer może potrzebować zbadać każdy element danych w całym drzewie, aby zlokalizować pojedynczą informację w tej konfiguracji.Natomiast najbardziej wydajne drzewo binarne jest takie, w którym każdy węzeł z wyjątkiem tych na dole drzewa ma dwoje dzieci i gdzie wszystkie węzły liściowe, dolne węzły w drzewie, znajdują się w tej samej odległości od korzenia.