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 drzew 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. Dany węzeł jest ACCEprzedzierane przez te powyżej w drzewie i zapewniają dostęp do osób poniżej.

Struktury danych binarnych drzew pozwalają każdemu węzłowi mieć nie więcej niż dwoje dzieci. 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 nakładają również żadnych ograniczeń dotyczących tego, jak wartości przechowywane w węzłach zawierających drzewo są ułożone.

Struktury danych są najbardziej przydatne, gdy poprawiają prędkość, z jaką można uzyskać dostęp do komputera, a do poprawy ich wydajności wykorzystywane są zmodyfikowane wersje drzew binarnych. 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ść wwęzeł podstawowy. To 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.