当前位置:天才代写 > tutorial > 大数据教程 > 数据结构之AVL树

数据结构之AVL树

2021-02-24 12:14 星期三 所属: 大数据教程 浏览:7

1. 简述

AVL树是最开始明确提出的自平衡二叉树,在AVL树中一切连接点的2个子树的高宽比较大 区别为一,因此它也被称作高宽比平衡树。AVL树而出名于它的发明人G.M. Adelson-Velsky和E.M. Landis。AVL树种搜索、插进和删掉在均值和最坏状况下全是O(log n),提升和删掉很有可能必须根据一次或数次树转动来再次均衡这一树。文中详细介绍了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树的操作过程是转动,有四种转动方法,各自为:左转动,右转动,上下转动(先左后右),右左转动(先后右左),事实上,这四种转动实际操作两组对称性,因此还可以称作两大类转动实际操作。

基础的算法设计:

typedef  struct  Node* Tree;
typedef  struct  Node* Node_t;
typedef  Type int;
struct  Node{
 Node_t left;
 Node_t right;
 int  height;
 Type data;
};
int  Height(Node_t node) {
 return  node->height;
}

3.1 LL

LL状况必须左旋体处理,如下图所显示:

编码为:

Node_t RightRotate(Node_t a) {
 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));
 return  b;
}

3.2 RR

RR状况必须左旋体处理,如下图所显示:

编码为:

Node_t LeftRotate(Node_t a) {
 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));
 return  b;
}

3.3 LR

LR状况必须上下(先B左转动,后A右转动)旋处理,如下图所显示:

编码为:

Node_t LeftRightRotate(Node_t a) {
 a->left = LeftRotate(a->left);
 return  RightRotate(a);
}

3.4 RL

RL状况必须右左旋体处理(先B右转动,后A左转动),如下图所显示:

编码为:

Node_t RightLeftRotate(Node_t a) {
 a->right = RightRotate(a->right);
 return  LeftRotate(a);
}

4. AVL数的插进和删掉实际操作

(1) 插进实际操作:事实上便是在不一样状况下选用不一样的转动方法调节整棵树,实际编码以下:

Node_t Insert(Type x, Tree t) {
 if(t == NULL) {
   t = NewNode(x);
 } else  if(x < t->data) {
   t->left = Insert(t->left);
   if(Height(t->left) - Height(t->right) == 2) {
    if(x < t->left->data) {
     t = RightRotate(t);
    } else  {
     t = LeftRightRotate(t);
    }
  }
 } else  {
   t->right = Insert(t->right);
   if(Height(t->right) - Height(t->left) == 2) {
    if(x > t->right->data) {
     t = LeftRotate(t);
    } else  {
     t = RightLeftRotate(t);
    }
  }
 }
 t->height = Max(Height(t->left), Height(t->right))   1;
 return  t;
}

(2) 删掉实际操作:最先精准定位要删掉的连接点,随后用该连接点的右小孩的最左小孩更换该连接点,并再次调节以该连接点为根的子树为AVL树,实际调节方式跟插进数据信息相近,编码以下:

Node_t Delete(Type x, Tree t) {
 if(t == NULL) return  NULL;
 if(t->data == x) {
  if(t->right == NULL) {
   Node_t temp = t;
   t = t->left;
   free(temp);
  } else  {
   Node_t head = t->right;
   while(head->left) {
    head = head->left;
   }
   t->data = head->data; //just copy data
   t->right = Delete(t->data, t->right);
   t->height = Max(Height(t->left), Height(t->right))   1;
  }
  return  t;
 } else  if(t->data < x) {
  Delete(x, t->right);
  if(t->right) Rotate(x, t->right);
 } else  {
  Delete(x, t->left);
  if(t->left) Rotate(x, t->left);
 }
 if(t) Rotate(x, t);
}

5. 小结

AVL树是最开始的自平衡二叉树,对比于之后出現的平衡二叉树(红黑树,treap,splay树)来讲,它如今运用较少,但科学研究AVL树针对掌握后边出現的常见平衡二叉树具备关键实际意义。

6. 参考文献

(1) 算法设计(C语言版) 严蔚敏,吴黄伟著

(2) http://zh.wikipedia.org/wiki/AVL树

(3)http://www.cppblog.com/goodwin/archive/2011/08/08/152797.html

(4)http://www.asiteof.me/2010/06/avl/

 

    关键字:

天才代写-代写联系方式