Функция диапазона для значений в дереве сплайнов? - PullRequest
Новая
       48

Функция диапазона для значений в дереве сплайнов?

1 голос
/ 15 марта 2019

Я новичок в структурах данных. Я пытаюсь написать некоторый псевдокод для функции диапазона с деревьями сплайнов: Range(S, A, B), которая меняет S на набор всех его членов, для которых значение ключа C удовлетворяет A ≤ C ≤ B. Я знаю, что сплайс-деревья возникают типы бинарных деревьев поиска и реализовать свою собственную операцию splay. По сути, я пытаюсь вернуть диапазон значений между A и B. Однако у меня возникают проблемы с пониманием того, как я должен это делать, или где мне следует начинать, и какие условия я должен проверять. Я прочитал определение деревьев сопряжения и знаю, что они похожи на двоичные деревья поиска с алгоритмом перемещения вперед.

Это то, что я имею до сих пор: 

Algorithm Range(Array S, int A, int B): array Set
S = new array(size) //Initialize an empty array of some size
if (A > B) then return NULL

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

1 Ответ

0 голосов
/ 17 марта 2019

Согласно Википедии ,

Splay-дерево - это самонастраивающееся бинарное дерево поиска с дополнительным свойством, которое позволяет недавно получить доступ к недавно полученным элементам. Он выполняет основные операции, такие как вставка, поиск и удаление за время амортизации O (log n).

Однако, поскольку операция «splay» применяется только к случайным поискам, дерево можно рассматривать как обычное «дерево двоичного поиска».

Алгоритм становится, 

Range (BSTree T, int A, int B)
  int Array S

  S ← Empty array
  If A <= B then
    For each C in T
      If A <= C and C <= B then
        Append C to S
  Return S

То есть дерево T обходится по порядку; и для каждого элемента C, удовлетворяющего условию, элемент добавляется в массив S. Если ни один элемент не удовлетворяет условию, возвращается пустой массив.

For each, если он недоступен на языке реализации, может быть реализован с использованием алгоритма, описанного как по порядку 

inorder(node)
  if (node = null)
    return
  inorder(node.left)
  visit(node)
  inorder(node.right)

, где vist(node) - это место, чтобы проверить, соответствует ли элемент условию.

...