AVLtree

平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树(有别于AVL算法)
AVL树:它左右的两个子树高度差的绝对值不超过1,且左右两个子树都是平衡二叉树。

引入

在说平衡二叉树之前,我们先需要谈谈二叉排序树,详见我之前在《排序》中所写。当排序树构建出来过于“畸形”,两边不对称,极端一点就是一路下来毫无分叉,那么显然,它的时间复杂度就是n,为了避免这种情况或者说,为了找寻最优情况,我们希望我们构建出来的二叉树可以两边对称平衡一下,使其树的深度为logn而非n,为此,我们引入平衡二叉树的概念。

调整(旋转)

当每次插入一个结点后,我们根据这棵树的现状对它进行旋转操作,可以简单的分为:

单旋

在A结点的左孩子的左子树或者右孩子的右子树上插入结点。

直接将B结点提上来,再把离A最近的子树滑给A。

双旋

在A结点的左孩子的右子树或者右孩子的左子树上插入结点。

直接将C提到A、B之间,再把C的子树分别分给A、B所缺的位置。

删除

查找

现在平衡树中查找到关键字相同的结点p

删除

分以下几种情况:

  • 叶结点:直接删除就好
  • 单分支结点:把后面那个孩子结点接上来就好啦
  • 双分支结点:把这个双分支结点p的值,用其中序前驱结点q的值替代后,直接删掉结点q