数据结构之avl树

《数据结构之avl树》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构之AVL树1•基本概念AVL树的复杂程度真是比二叉搜索树高了整整一个数量级一一它的原理并不难弄懂，但要把它用代码实现出来还真的有点费脑筋。下面我们来看看：1.1AVL树是什么？AVL树本质上还是一棵二叉搜索树（因此读者可以看到我后面的代码是继承自二叉搜索树的），它的特点是：本身首先是一棵二叉搜索树。带有平衡条件：每个结点的左右子树的高度Z差的绝对值（平衡因子）最多为1。1.2.例如：3上图中，左边的是AVL树，而右边的不是。因为左边的树的每个结点的左右子树的高度之差的绝对值都最多为1,而右边的树由于结点6没有子树，导致根结点5的平衡因子为2。1.2为什

2、么要用AVL树？有人也许要问：为什么要有AVL树呢？它有什么作用呢？我们先来看看二叉搜索树吧（因为AVL树木质上是一棵二叉搜索树），假设有这么一种极端的情况：二叉搜索树的结点为1、2、3、4、5,也就是：5聪明的你是不是发现什么了呢？呵呵，显而易见一一这棵二叉搜索树其实等同于一个链表了，也就是说，它在查找上的优势已经全无了一一在这种情况下，查找一个结点的时间复杂度是0（N）!好，那么假如是AVL树（别忘了AVL树还是二叉搜索树），则会是：235可以看出，AVL树的查找平均时间复杂度要比二叉搜索树低一一它是0（logN）o也就是说，在大量的随机数据中AVL树的表

3、现要好得多。1.3旋转假设有一个结点的平衡因子为2（在AVL树中，最大就是2,因为结点是一个一个地插入到树中的，一旦出现不平衡的状态就会立即进行调整，因此平衡因子最大不可能超过2）,那么就需要进行调整。由于任意一个结点最多只有两个儿子，所以当高度不平衡时，只可能是以下四种情况造成的：1.对该结点的左儿子的左子树进行了一次插入。2.对该结点的左儿子的右子树进行了一次插入。3.对该结点的右儿子的左子树进行了一次插入。4.对该结点的右儿子的右子树进行了一次插入。情况1和4是关于该点的镜像对称，同样，情况2和3也是一对镜像对称。因此，理论上只有两种情况，当然了，从编程

4、的角度来看述是四种情况。第一种情况是插入发牛在“外边”的情况（即左-左的情况或右-右的情况），该情况可以通过对树的一次单旋转来完成调整。第二种情况是插入发生在“内部”的情况（即左-右的情况或右-左的情况），该情况要通过稍微复杂些的双旋转来处理。1.3.1单旋转情况1：对该结点的左儿子的左子树进行了一次插入。左边为调整前得节点，我们可以看出k2的左右子树己不再满足AVL平衡条件，调整后的为右图。我们可以看出，解决办法是将x上移一层，并将z下移一层，由于在原树中k2>kl,所以k2成为kl的右子树，而y是小于k2的，所以成为k2的左子树。为了设计算法，我们这里來看

5、一个更易理解的：插入的是节点“6”算法设计：由于是情形1对该结点的左儿子的左子树进行了一次插入，该节点是“8”，首先我们不考虑其父节点的情况，因为我们创建节点是递归创建的，可以不用考虑其父节点与其的连接,这在后面递归创建的时候会说到，由于“8”的右孩子将不会发生变化，但是其左孩子设为"7”的右孩子，将7的右孩子设为“8”及其子树，然后返回“7”节点的指针。实现代码：//情形1AVLTreeSingleRotateWithLeft（PAVLNodek2）PAVLNodek1;kl=k2->1;k2->1=kl->r;kl->r=k2;k2->h=MAX(Heig

6、ht(k2->1),Height(k2->r))+1；k1->h=MAX(Height(kl->l),k2->h)+1;returnkl;/*Newroot*/)情况4：对该结点的右儿子的右子树进行了一次插入。左边为调整前得节点，我们可以看出kl的左右子树己不再满足AVL平衡条件，调整后的为右图。我们可以看出，解决办法是将z上移一层，并将x下移一层，由于在原树中k2>kl,所以kl成为k2的左子树，而y是大于kl的，所以成为kl的右子树。为了设计算法，我们这里來看一个更易理解的：插入的是节点“6”算法设计：由于是情形1对该结点的右儿子的右子树进行了一次插入，该

7、节点为“4”，我们同第一种情形类似。实现代码：//情形4AVLTreeSingleRotateWithRight(PAVLNodekl){PAVLNodek2;k2=kl->r;kl->r=k2->l;k2->l=kl;kl->h=MAX(Height(k1->1),Height(kl->r))+1;k2->h=MAX(Height(k2->r),kl->h)+1;returnk2;/*Newroot*/}1.3.2双旋转情况2：对该结点的左儿子的右子树进行了一次插入。这种情况是单旋转调整不回来的，如下图：图（1）图（2）这里我们将图（1）的Y子树看成如图（2

8、）,以k2为子树根节点的树，我们将其子