Я реализовал двоичное дерево поиска, и я хочу добавить больше функциональности в свою функцию вставки, чтобы сделать его самобалансирующимся деревом. Я кодирую в С#.
Может ли кто-нибудь предложить мне хорошие уроки или ссылки на это? Я сделал несколько поисков и нашел некоторые ссылки, но ни один из них не был достаточно описательным.
Спасибо.
Существует множество алгоритмов для самоустанавливающихся деревьев поиска, многие из которых являются сложными, а другие из них довольно просты (хотя и с некоторыми оговорками).
Книга "Введение в алгоритмы, второе издание" Cormen, Leisserson, Rivest и Stein - отличное введение в алгоритмы и покрытия красные/черные деревья очень хорошо. Это также отличная книга в целом по алгоритмам и структурам данных.
Если вы заинтересованы в использовании splay trees, которые чрезвычайно быстры и на самом деле довольно просты в реализации, оригинальная бумага в структуре данных является очень доступной. Кроме того, он включает в себя доказательство всех границ времени выполнения.
treap - это простое рандомизированное сбалансированное двоичное дерево поиска, которое можно реализовать довольно легко, как только вы знаете, как реализовать вращения дерева. Вращения деревьев также используются в деревьях splay, и поэтому, возможно, стоит изучить.
Для деревьев AVL, эта лекция кажется хороший ресурс.
Надеюсь, это поможет!
проверить http://code.google.com/p/self-balancing-avl-tree/, реализует самобалансирующееся avl-дерево в С#. плюс он также реализует операции конкатенации и разделения.