Должны ли красно-черные деревья быть отсортированы?

У меня есть довольно простой вопрос: Должны ли красно-черные деревья быть отсортированы? Я спрашиваю об этом, потому что маленькая коробочка в правой части страницы Википедии (http://en.wikipedia.org/wiki/Red-black_tree) говорит, что время поиска равно O (log (n)); однако это будет верно только в том случае, если дерево Отсортировано. С другой стороны, свойства s

4 2
red-black-tree

4 ответа:

Красный черный деревья сортируются деревьев (все деревья РБ сортируются бинарные деревья, но не все сортированные бинарные деревья красно черные деревья тоже). Разница между простым бинарным деревом и красным черным деревом заключается в том, что деревья RB гарантируют , что время поиска будет log2(n) потому что они сбалансированы. По сути, это гарантирует, что количество слоев дляn узлов никогда не будет больше log2(n) , сохраняя двоичный поиск в проверять.

Простое двоичное дерево без балансировки не всегда будет производить лог 2(n) временная сложность. Например, если у меня есть такое дерево: 

  4
 / \
3   6
     \
      7
       \
       10
         \
         12
Для этого несбалансированного дерева фактическое время поиска почти линейно, чтобы найти 12 (наихудшая временная сложность, 5 сравнений). Для сбалансированного дерева, которое имеет не более log2(n) слои, дерево выше может быть: 
     7
   /   \
  4    10
 / \     \
3   6    12

И поэтому поиск любого из узлов нижнего слоя займет не более 3 сравнения (что соответствует логу 2(n) поскольку он фактически округлен, ceil[log2(6)] = 3)

Здесь важно помнить, что количество слоев функционально эквивалентно количеству сравнений, которые вы должны сделать, когда начинаете с корня. Красно-черные деревья ограничивают количество слоев до минимума с помощью балансировки, в то время как ванильные, несбалансированные бинарные деревья этого не делают.
5

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

2

Красно-черные деревья имеют время поиска O(log n) из-за его способа установки их узлов с естественным порядком.

Когда вы делаете сравнение узлов, вы теоретически отбрасываете половину вариантов, когда вы берете ветвь.

Так как вы можете только "наполовину" log n times, прежде чем вы доберетесь до одного элемента, то ваша сложность поиска составляет O(log n)

1

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

1