Разница между различными типами ADT дерева, отличными от двоичного дерева

Question

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

1. В-дерева
2. B + дерево
3. к-ичное дерево
4. кД дерево
5. п-ичное дерево
6. четырехъядерного дерево
7. 2-3 дерево
8. 2- 3-4 дерева
9. m-Tree
10. m-ary tree

Единственные деревья, которые имеют очень четкое определение и не перекрываются, представляют собой двоичные, двоичные деревья поиска и, возможно, даже попытки.

Помимо этих результатов поиска Google для указанных выше деревьев приводят к множеству различных определений, некоторые перекрываются, некоторые из них очень отличаются друг от друга. Например, реализация b-дерева одним человеком настолько отличается от другого; что он буквально призывает к изменению определения. Это дошло до того, что все эти определения только начали путать меня со мной. Есть ли книга для всех вышеупомянутых структур данных дерева, которые можно считать стандартной библией? Некоторое разъяснение будет с благодарностью оценено.

Answer 1

Большинства, хотя, возможно, не все из них находятся в Ахо, Hopcroft и Ульман в структурах данных и алгоритмы

намек, что ничего с -ичным в этом имени является деревом с определенными разветвлениями степени - так двоичное дерево имеет два (возможно, нулевых) дочерних элемента на узел; дерево n -ary имеет n (возможно, null) детей на узел.

Большинство других в списке имеют своего рода балансировку в своем определении - и алгоритмах - чтобы сохранить их худшее поведение в O (n log n), тогда как без балансировки они обычно имеют худшее поведение O (n^2)

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