seach для конкретного узла в дереве RB

Question

Предположим, у меня есть дерево RB, состоящее из чисел, которые соответствуют возрасту людей; и предположим, что у каждого узла также есть пол (самка или мужчина).

Вопрос в том, как получить конкретное число из этого дерева с использованием значения OS-SELECT и рангов? Определенное число означает, найти второго младшего человека в дереве.

Пример: OS-SELECT (корень, 2), который возвращает второго младшего человека из дерева.

Цель не просто найти 2--й или третий узел yougest, цель состоит в том, чтобы найти 2-ой младшие мужчина или 2 младших женщина

Answer 1

Просто обход дерева в порядка и количество элементов, которые удовлетворяют предикат. В этом случае предикат будет «мужским». Нахождение элемента в бинарном дереве поиска позволяет закончить обход рано, что не обязательно тривиально для реализации, так вот простой псевдокод для алгоритма:

# return value is used to track how many matching nodes must be 
# found until the k'th one is reached 
int OS-SELECT(node, rank) 
    if not node  # leaf reached? 
    return rank  # Keep searching. 
    rank = OS-SELECT(node.left, rank) 
    if not rank  # Node was found in left subtree. 
    return 0   # End early. 
    if predicate(node) # Test the predicate. 
    if not --rank # The node matches: There are less matches to go through. 
     visit(node) # Rank dropped to 0: Found it. Visit the node and 
     return 0  # end early. 
    return OS-SELECT(node.right, rank)