binary-tree - 分页二叉树与 AVL 树和/或 B 树

Question

分页二叉树与 AVL 树和/或 B 树有何不同？

Answer 1

In spite of the different structure of AVL and B-tree as stated by Konrad, usage of AVL and B-tree is also different, I think. B-tree generally used to implement indexing. Purpose of employing B-tree is to reduce disk I/O, while data of AVL-tree often resists totally in memory instead of partially in memory partially on disk like B-tree. Purpose of AVL-tree is to avoid the appearance of left/right branch tree in some extreme situation ensuring a perfect O(logn) time complexity when doing search operation.

Answer 2

我建议阅读有关该主题的优秀维基百科文章。

非常简短：

• AVL 树是二叉搜索树（即用于对其元素进行排序的二叉树）。不同之处在于 AVL 树实现了一种自平衡策略来均匀分布节点以减少树的最大深度。
• B 树是二叉搜索树的推广，即它们不再是二叉的。