来自"NOCOW"

目录 1 平衡树 2 分类 2.1 内结点存储方式 2.2 叶结点存储方式 3 引用

[编辑] 平衡树

通常我们将结点数为n且时间复杂度为O(log n)的树称为平衡树。

具有平衡树性质的二叉搜索树称为平衡二叉搜索树（平衡二叉搜索树可以理解为二叉平衡树），即它的渐进形态接近于近似满二叉搜索树。

[编辑] 分类

按照集合中元素在树结点中的存储方式，可将平衡树分为

[编辑] 内结点存储方式

将树中所有结点（内结点和叶结点）都用于存储结合中的元素。

• 典型代表：红黑树

[编辑] 叶结点存储方式

只用叶结点存储集合中的元素，内结点用来存储引导搜索的键值等信息。

• 典型代表：2-3-4树

[编辑] 引用

算法与数据结构（第二版） 傅清祥、王晓东编著