数据结构-平衡二叉树

平衡二叉树,未完待续…

平衡二叉树

概念

平衡树是二叉搜索树和堆合并构成的数据结构,它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。平衡二叉树必定是排序二叉树,反之不一定。

优势

平衡二叉树的目的是为了减少二叉查找树层次,提高查找速度。

对一棵查找树(search tree)进行查询/新增/删除等动作, 所花的时间与树的高度h成比例, 并不与树的容量n成比例。如果可以让树维持矮矮胖胖的好身材, 也就是让h维持在O(lg n)左右, 完成上述工作就很省时间。能够一直维持好身材, 不因新增删除而长歪的搜寻树, 叫做balanced search tree(平衡树)。

种类

1.红黑树 2.AVL树 3.SBT 4.Treap 5.伸展树

下面进行较为详细的说明。

红黑树

红黑树就是一种自平衡的二叉查找树,说他平衡的意思是他不会变成“瘸子”,左腿特别长或者右腿特别长。除了符合二叉查找树的特性之外,还具体下列的特性:

  1. 每一个结点要么是红色,要么是黑色。
  2. 根结点是黑色的。
  3. 所有叶子结点都是黑色的(实际上都是Null指针,下图用NIL表示)。叶子结点不包含任何关键字信息,所有查询关键字都在非终结点上。
  4. 每个红色结点的两个子节点必须是黑色的(从每个叶子到根的所有路径上不能有两个连续的红色结点)。
  5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
    1. 也就是说,如果一个结点存在黑孩子结点,那么该节点肯定有两个黑孩子结点。

另外,红黑树并不是一个完美平衡二叉查找树,任意一个结点到每个叶子结点的路径都包含数量相同的黑结点(性质5)。所以我们叫红黑树这种平衡为黑色完美平衡

红黑树自平衡

前面讲到红黑树能自平衡,它靠的是什么?三种操作:左旋、右旋和变色。

  • 左旋:以某个结点作为支点(旋转结点),其右子结点变为旋转结点的父结点,右子结点的左子结点变为旋转结点的右子结点,左子结点保持不变。
  • 右旋:以某个结点作为支点(旋转结点),其左子结点变为旋转结点的父结点,左子结点的右子结点变为旋转结点的左子结点,右子结点保持不变。
  • 变色:结点的颜色由红变黑或由黑变红。

由上图可知:旋转操作不会影响旋转结点的父结点,父结点以上的结构还是保持不变的。若想进一步了解请点击这里

红黑树查找

归根结底,红黑树是一棵二叉搜索树,所以查找遵循二叉搜索树的规则即可。

红黑树插入

插入操作包括两部分工作:一查找插入的位置;二插入后自平衡。

红黑树删除

AVL树

平衡二叉查找树,又称 AVL树。 它除了具备二叉查找树的基本特征之外,还具有一个非常重要的特点:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值(平衡因子 ) 不超过1。 也就是说AVL树每个节点的平衡因子只可能是 -1、0和1。

SBT树

Treap树

伸展树

您的每一份支持将鼓励我继续创作!
-------------本文结束感谢您的阅读-------------