常见数据结构之树.pdfVIP

1.概述

AVL树是最早自平衡二叉树，在AVL树中任何节点的两个子树的高度最

大差别为一，所以它也被称为高度平衡树。AVL树得名于它的发明者G.M.

Adelson-Velsky和E.M.Landis。AVL树种查找、和删除在平均和情

况下都是O（logn），增加和删除可能需要通过一次或多次树旋转来重新平衡

这个树。本文介绍了AVL树的设计思想和基本操作。

2.基本术语

有四种种情况可能导致二叉查找树不平衡，分别为：

（1）LL：一个新节点到根节点的左子树（Left）的左子树（Left），导致

根节点的平衡因子由1变为2

（2）RR：一个新节点到根节点的右子树（Right）的右子树（Right），导

致根节点的平衡因子由-1变为-2

（3）LR：一个新节点到根节点的左子树（Left）的右子树（Right），导

致根节点的平衡因子由1变为2

（4）RL：一个新节点到根节点的右子树（Right）的左子树（Left），导

致根节点的平衡因子由-1变为-2

针对四种种情况可能导致的不平衡，可以通过旋转使之变平衡。有两种基本的

旋转：

（1）左旋转：将根节点旋转到（根节点的）右孩子的左孩子位置

（2）右旋转：将根节点旋转到（根节点的）左孩子的右孩子位置

3.AVL树的旋转操作

AVL树的基本操作是旋转，有四种旋转方式，分别为：左旋转，右旋转，左右

旋转（先左后右），右左旋转（先右后左），实际上，这四种旋转操作两两对

称，因而也可以说成两类旋转操作。

基本的数据结构：

typedefstructNode*Tree;

typedefstructNode*Node_t;

typedefTypeint;

structNode{

Node_tleft;

Node_tright;

intheight;

Typedata;

};

intHeight(Node_tnode){

returnnode-height;

}

3.1LL

LL情况需要右旋解决，如下图所示：

代码为：

Node_tRightRotate(Node_ta){

b=a-left;

a-left=b-right;

b-right=a;

a-height=Max(Height(a-left),Height(a-right));

b-height=Max(Height(b-left),Height(b-right));

returnb;

}

3.2RR

RR情况需要左旋解决，如下图所示：

代码为：

Node_tLeftRotate(Node_ta){

b=a-right;

a-right=b-left;

b-left=a;

a-height=Max(Height(a-left),Height(a-right));

b-height=Max(Height(b-left),Height(b-right));

returnb;

}

3.3LR

LR情况需要左右（先B左旋转，后A右旋转）旋解决，如下图所示：

代码为：

Node_tLeftRightRotate(Node_ta){

a-left=LeftRotate(a-left);

returnRightRotate(a);

}

3.4RL

RL情况需要右左旋解决（先B右旋转，后A左旋转），如下图所示：