Где найти сбалансированную реализацию дерева?

Question

Мне было интересно, знает ли кто-нибудь где-нибудь в Интернете, где я могу скопировать и вставить (в целях обучения) реализацию двоичного дерева поиска, которое реализует как балансировку, так и алгоритм, чтобы спросить, сколько узлов меньше, чемконкретное значение.Я хочу иметь возможность запросить эту структуру данных и спросить "Сколько узлов

Я предпочитаю реализации в Python, C, C ++ или Java, но другие приветствуются.

Answer 1

Если это все еще актуально, вы можете поддерживать в каждом узле размер поддерева, как в

http://www.codeproject.com/script/Articles/ViewDownloads.aspx?aid=12347&zep=HeightBalancedTree.h&rzp=%2fKB%2farchitecture%2favl_cpp%2f%2favl_cpp.zip

Обратите внимание на функцию FindComparable .Если объект найден, он возвращает свой индекс (количество узлов, которые меньше, чем искомый объект).

В случае, если искомый объект не находится в дереве, вы хотите получить индекс минимальногоузел, который больше, чем искомый объект.

Обратите внимание, что происходит с индексом, когда объект не найден.Последний Node :: GetSize (Node :: GetRight (узел))) или Node :: GetSize (Node :: GetLeft (узел))) будет оценен в 0, поэтомуу вас есть 2 случая:

• Если последний поворот был прав (cmp> 0), вы получите индекс максимального узла, который меньше искомого объекта плюс один -это именно то значение, которое вы хотите.
• Если последний ход остался (cmp <0), вы получите индекс минимального узла, который больше искомого объекта <strong>минус один .

Следовательно, вместо возврата Size () , когда объект не был найден, вы можете вернуть:

index + (cmp < 0)?1:0;