平衡二叉树的自平衡策略

Time: 二月 11, 2011
Category: Programming practices

本文的目的,旨在为数据结构或者算法的设计提供一些启发性的思路。

数组 --> 二分搜索 --> 链表 --> 二叉搜索树

二分搜索

二分搜索是一种很重要的算法。最普遍的莫过于对排序数组的处理。而数组的一个特质,使得二分搜索在离散存储结构里难以实现

  • 连续的内存区域,依靠下标来自动计算偏移量

就是说,对排序数组的操作,仅仅依靠下标就可以进行的。但是在实际的系统中,我们有时无法一次性提供足够大的连续存储空间或者海量处理那些离散地存储在内存里的数据的时候,如链表等等,这种方法不适用。

回想一下对排序数组进行二分搜索的操作,每次二分是不是都在最中间进行,那链表该如何才能做到呢?

答案是,做不到吧。离散的本质就是随机,你不可能找到中结点的位置。二叉搜索树的出现解决了这个问题,直接从中结点出发和决定下一分支。

所以现在的问题是:谁来担任中结点。

  1. 对于静态的数据,递归选举中结点,然后形成最优二叉搜索树
  2. 对于动态的数据,关键的地方在于,当插入一个结点或者删除一个结点的时候,如何平衡整个二叉搜索树的二分结构。

所以出现了自平衡,解决了二分搜索思想在离散存储结构里的应用。

自平衡的策略

所谓自平衡是指通过执行一系列维持某种性质的操作,这个性质,是为了更好的实现二分搜索的思想。如AVL的平衡因子,红黑树的5个强制约束,等等。

而旋转操作则是实现自平衡最常用的一项策略,通过左右子树迁移结点以实现结构的动态平衡

左旋,相当于右子树往左字树迁移两个结点,右旋同理。下面以红黑树为例,讨论自平衡策略的实现

旋转的时机

左右子树的结点数不想等时结构处于不平衡状态,不平衡就要旋转。但具体的实现取决于不同的场景和需求,由结构自身的性质来决定的。如AVL树在当左右子树结点总数相差1时进行旋转,(待)

Leave a Comment