Zaimplementowałem binarne drzewo wyszukiwania i chcę dodać więcej funkcjonalności w jego funkcji wstawiania, aby uczynić z niego drzewo samowyrównujące. Koduję w języku C#.Wdrażanie zrównoważonego drzewa wyszukiwania binarnego?
Czy ktoś może zaproponować mi dobre tutoriale lub linki na ten temat? Zrobiłem kilka wyszukiwań i znalazłem kilka linków, ale żadna z nich nie była wystarczająco opisowa.
Dzięki.
Istnieje wiele algorytmów samokontrolujących się drzew wyszukiwania, z których wiele jest złożonych, a inne są dość proste (aczkolwiek z pewnymi zastrzeżeniami).
Książka "Wprowadzenie do algorytmów, drugie wydanie" autorstwa Cormena, Leissersona, Rivesta i Steina jest znakomitym wprowadzeniem do algorytmów i obejmuje bardzo dobrze red/black trees. To także świetna książka na temat algorytmów i struktur danych.
Jeśli interesuje Cię korzystanie z splay trees, które są niezwykle szybkie i właściwie łatwe do wdrożenia, original paper on the data structure jest bardzo łatwo dostępny. Ponadto zawiera dowód wszystkich ograniczeń czasu pracy.
jest prostym, zrandomizowanym zbalansowanym drzewem wyszukiwania binarnego, które można łatwo wdrożyć, gdy wiesz, jak zaimplementować tree rotations. Rotacje drzew są również używane w drzewach do gry, więc warto je zbadać.
Dla AVL trees, this lecture wydaje się być dobrym źródłem informacji.
Mam nadzieję, że to pomoże!
Wyewidencjonowanie http://code.google.com/p/self-balancing-avl-tree/, implementuje samorozliczalne drzewo avl w C#. ponadto implementuje operacje łączone i dzielone.
Jakie dane przechowujesz w drzewie i dlaczego? –
Proponuję, aby spojrzeć na czerwone czarne drzewo. –
Szukałbym drzewek AVL. AFAIK są łatwiejsze do wdrożenia niż czerwono-czarne drzewa. – CodesInChaos