#data-structures
#структуры данных
Вопрос:
Мне было интересно, знает ли кто-нибудь где-нибудь в Интернете, где я могу скопировать и вставить (в учебных целях) реализацию двоичного дерева поиска, которое реализует как балансировку, так и алгоритм, чтобы спросить, сколько узлов меньше определенного значения. Я хочу иметь возможность запрашивать эту структуру данных и спрашивать: «Сколько узлов < x в этой структуре данных?» Вся цель состоит в том, чтобы ответить на этот последний тип запроса, но балансировка также важна, потому что я хочу иметь возможность обрабатывать большие несбалансированные последовательности записей.
Я предпочитаю реализации на Python, C, C или Java, но приветствуются и другие.
Комментарии:
1. Нет, не совсем. Я хочу скопировать и вставить это, чтобы понять базовые алгоритмы. Тогда я мог бы также использовать это как строительный блок алгоритма, который я пытаюсь написать.
Ответ №1:
Если это все еще актуально, вы могли бы поддерживать в каждом узле размер поддерева, как в
Обратите внимание на функцию FindComparable . Если объект найден, он возвращает его индекс (количество узлов, которые меньше, чем искомый объект).
В случае, если искомого объекта нет в дереве, вы хотите получить индекс минимального узла, который больше искомого объекта.
Обратите внимание, что происходит с индексом, когда объект не найден. Последний узел::getSize(Узел::GetRight(узел))) или узел ::getSize(узел::getLeft(узел)))будет оценено как 0, так что у вас есть 2 случая:
- Если последний поворот был правильным (cmp> 0), вы получите индекс максимального узла, который меньше искомого объекта плюс один — это именно то значение, которое вы хотите.
- Если остался последний ход (cmp < 0), вы получите индекс минимального узла, который больше, чем искомый объект минус один.
Поэтому вместо возврата Size(), когда объект не был найден, вы могли бы вернуть:
index (cmp < 0)?1:0;