赵玉伟的博客

树的平衡性与稳定性

什么是平衡性

平衡性是指一棵树的任意节点的左子树的高度和右子树的高度的差值, 差值越小,平衡性越好, 最好的情况就是相等(差值为0)。
平衡性的意义:最大限度的提高访问效率。

什么是稳定性

稳定性是指将任意序列构造成一棵树的过程中, 新插入的节点不会对已经插入的节点的值造成改变。
用一个例子说明:
将1,2,3,4,5,6,7,8,9 构造成一棵二叉查找树的过程中,为了维持左子树和右子树的高度保持基本一致, 需要每插入一个节点,就要调整父节点以及其他节点的值,那么这样的数据构造成数的过程中, 数据是不稳定的。调整的方式有专业的术语, 叫左旋转,右旋转。
试想一下,如果插入数据的量级越大(比如数据库的数据和索引), 需要移动的数据量也会越大,插入效率会很低。

稳定性和平衡性是一对天敌, 最好的办法是两者兼顾,达到基本平衡和基本稳定。

平衡二叉树

平衡二叉树的目的是为了追求极度平衡, 从而牺牲树的稳定性。插入一个节点数值的过程中,甚至会影响到根节点。所以,稳定性很差。如果每个节点按顺序存储多个值,那么就变成了另外一种数据结构–平衡查找树(有B tree, B+ tree),操作系统一般用这种数据结构进行存取; 另外,mysql的innodb引擎,也是用这种数据结构进行数据存取的。

红黑树

红黑树是平衡二叉树的一个子集, 也就是每次插入一个节点数据的时候, 为了达到树的平衡, 会在一定范围内做数据的调整,只会影响其父节点以及兄弟节点的数据,从而既实现树基本平衡,又可以保证树的基本稳定,目前红黑树的应用场景比较多,java中的TreeMap底层便是通过红黑树实现的。

要想理解红黑树, 最好先理解什么是2-3树,因为红黑树是通过2-3树变相的实现的。 如果单靠概念是比较难理解的。

2-3树

任意一个节点可以最多有两个子节点, 那么叫做二叉树; 任意一个节点可以有0个节点、1个节点、2个节点、3个节点,那么可以叫做2-3树。

如果一个节点有两个子节点, 那么父节点的值只有一个, 也就是 left < parent <= right; 如果一个节点有三个节点, 那么父节点的值有三个, 也就是 left < parent1 <= middle < parent2 <= right;

网上有一篇比较好的博文:
2-3树的构造与分裂

通过这篇博文,可以理解2-3树以及红黑树。