AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一,所以它也被称为高度平衡树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis,他们在 1962 年的论文 “An algorithm for the organization of information” 中发表了它。
其中AVL树主要的操作包括:左旋、右旋、两种情况的双旋转。下面先给出旋转的示意图:
单旋:
两种情况的双旋:
下面,根据上述的旋转示意图编写递归的代码:
struct AvlNode{ int val, height; AvlNode*l, *r; AvlNode() :val(-1), height(-1), l(NULL), r(NULL){}; AvlNode(int x) :val(x), height(0), l(NULL), r(NULL){}; }; static int Height(AvlNode* T) {//求高度 if (T == NULL) return -1; else return T->height; } static AvlNode* SingleRotateLeft(AvlNode* k2) {//左旋,把树顺时针旋转 AvlNode*k1 = k2->l; k2->l = k1->r; k1->r = k2; //注意更新高度 k2->height = max(Height(k2->l), Height(k2->r)) + 1; k1->height = max(Height(k1->l), k2->height) + 1; return k1; } static AvlNode* SingleRotateRight(AvlNode* k1) {//右旋,把树逆时针旋转 AvlNode*k2 = k1->r; k1->r = k2->l; k2->l = k1; //注意更新高度 k1->height = max(Height(k1->l), Height(k1->r)) + 1; k2->height = max(Height(k2->r), k1->height) + 1; return k2; } static AvlNode* DoubleRotateLeft(AvlNode* k3) {//先把k2(k3->l)逆时针旋转,再把k3顺时针旋转 k3->l = SingleRotateRight(k3->l); return SingleRotateLeft(k3); } static AvlNode* DoubleRotateRight(AvlNode* k1) {//先把k2(k1->r)逆时针旋转,再把k1顺时针旋转 k1->r = SingleRotateLeft(k1->r); return SingleRotateRight(k1); } static AvlNode* Insert(int x, AvlNode*T) { if (T == NULL)//如果节点为空,则新建一个节点 T = new AvlNode(x); else if (x < T->val) {//x小于T的值,则插入左边 T->l = Insert(x, T->l); if (Height(T->l) - Height(T->r) == 2) {//插入后,左边比右边高2,则需要调整 if (x < T->l->val)//如果插入的值是在左子树的左边,则左旋即可 T = SingleRotateLeft(T); else//如果插入的值是在左子树的右边,那么需要双旋转 T = DoubleRotateLeft(T); } } else if (x > T->val) {//如果插入的值大于T的值,则插入T的右子树中 T->r = Insert(x, T->r); if (Height(T->r) - Height(T->l) == 2) {//高度差为2,需要调整 if (x>T->r->val)//如果在右子树的右边,单选即可 T = SingleRotateRight(T); else//在右子树的左边,需要双旋 T = DoubleRotateRight(T); } } //注意更新高度 T->height = max(Height(T->l), Height(T->r)) + 1; return T; }