AVL Tree vs Balanced Tree

Question

Дерево AVL - хорошо известная структура данных внутренней памяти, тогда как Сбалансированное дерево - это известная структура данных внешней памяти. Почему мы не можем использовать Сбалансированные деревья для внутренней памяти?

Answer 1

Вы очень любите можете иметь сбалансированные деревья во внутренней памяти. Дерево AVL - это просто один тип сбалансированного дерева, а также другие, такие как красно-черные и 2-3-4 дерева.

Итак, я не уверен , где вы получили идею, что сбалансированные деревья не могут существовать во внутренней памяти, но я бы передумал, если бы я был вами.

И, на самом деле, вы можете поместить дерево AVL на диск, если вы так наклонены.

---

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

root node -, 
      | 
      V 
+------+------+------+ 
| Val1 | Val2 | val3 | 
+------+------+------+ 
/  |  |  \ 
<other nodes down here> 

Это отличается от более общего термина «сбалансированное дерево», и они часто используются в дисковых ситуациях, вы, как правило, хотят, чтобы читать/писать целые блоки/кластеров/секторов в то время.

Итак, если вы можете поместить десять значений в блок диска, более эффективно использовать BTree (тогда как память не имеет понятия размера блока, поэтому может быть предпочтительнее использовать более простой алгоритм - BTrees должны сочетаться оба дерева поиска, чтобы найти узел и линейный/двоичный поиск, чтобы найти значение в узла).

Но, в то время как BTrees может быть типа сбалансированного дерева, это снова только один типа.