Доступ к красно-черному дереву по порядковому индексу - PullRequest
Новая
       41

Доступ к красно-черному дереву по порядковому индексу

2 голосов
/ 31 марта 2012

У меня красно-черное дерево (бинарное дерево, все листья в пределах 2-х уровней). Я могу перемещаться по узлам: влево, вправо или родитель. Я знаю все количество узлов.

Я должен найти N-й самый маленький элемент в дереве. Есть ли способ сделать это быстрее, чем в O (n)? Есть идеи по оптимизации доступа по индексу?

Ответы [ 3 ]

3 голосов
/ 31 марта 2012

В каждом узле X вы должны хранить количество узлов в поддереве с X в качестве корня. 

count(LEAF) = 1
count(NODE) = count(NODE->LEFT) + count(NODE->RIGHT) + 1

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

После этого решение простое 

NODE nth(NODE root, int n) {
    if (root->left->count <= n) return nth(root->left, n);
    if ( root->left->count + 1 == n) return root;
    return nth(root->right, n - root->left->count - 1);
}
2 голосов
/ 31 марта 2012

вы можете добавить один атрибут в каждом узле, который показывает количество дочерних элементов этого узла.с помощью этого атрибута вы можете найти N-й наименьший узел с O (lgn).

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

1 голос
/ 25 мая 2017

Для красно-черного дерева вам не нужно отслеживать количество узлов слева, потому что, если оно смещено вправо (должно быть), то количество левых узлов всегда будет формировать ряд Мерсенна (1, 3, 7, 15 31 ...) или 2^depth -1.

Имея это в виду, мы можем записать логику для рекурсивного получения узла. Принятый ответ выше помечен знаком . Это правильная реализация в эликсире. Для упаковки 

def nth(%Rbtree{node: r}, n), do: do_nth(r, n)
defp do_nth({_,h,k,v,l,r}, n) do
  l_count = left_count(h)
  cond do
    l_count > n ->
      case l do
        nil -> {k,v}
        _ -> do_nth(l, n)
      end
    l_count == n -> {k,v}
    true ->
      case r do
        nil -> {k,v}
        _ -> do_nth(r, n - l_count - 1)
      end
  end
end
defp left_count(1), do: 0
defp left_count(0), do: 0
defp left_count(h), do: :math.pow(2,h-1)-1 |> round
...