Chinaunix首页 | 论坛 | 博客

分类: C/C++

2018-06-14 16:37:39

avltree, 平衡二叉查找树,是一种特殊情况下的二叉查找树,它的特殊之处在于,对于每一个节点,其左子树深度和右子树深度之差的绝对值不大于1.

自从上次写完BSTree后,心里想写AVL树了,查了点资料,感觉自己之前的结构是真的low,哎,知耻而后勇,先说一下这次的avl与上次bstree的两点不同:

1)节点数据结构中新增了一个高度变量,代码如下:



点击(此处)折叠或打开

  1. struct Node{
  2.     struct Node *left;
  3.     struct Node *right;
  4.     int val;
  5.     int height;
  6.     Node(int x):val(x), height(1), left(NULL), right(NULL){}
  7. };

2)逻辑上,该树的根节点,多了一个父节点,该父节点没有实际意义,只是为了方便后续的所有关于该树的增删改查(别想到数据库。。。)的操作。形式如下图:





之后就要开启我们的插入和删除操作了,为什么没有查找?由于avl是一种bst,所以查找操作不在此赘述。

插入时,由于要保证平衡这一性质,所以要针对不同不平衡情况进行分别处理,其中,不平衡的情况分为左左失衡,右右失衡,左右失衡,右左失衡,下面进行分情况讨论处理,这里有一点需要说明的是,以上四种情况都要找到,发生不平衡的最低的树节点。

左左失衡:情况如图:

调整后的结果如下图:



代码奉上:

点击(此处)折叠或打开

  1. struct Node *avltree::ll_rotate(struct Node *y){
  2.     struct Node *x = y->left;
  3.     y->left = x->right;
  4.     x->right = y;
  5.     y->height = std::max(getHeight(y->left), getHeight(y->right)) +1;
  6.     x->height = std::max(getHeight(x->left), getHeight(x->right)) +1;
  7. return x;}

右右失衡情况如下图:

调整后如下图:


代码奉上:

点击(此处)折叠或打开

  1. struct Node *avltree::rr_rotate(struct Node *y){
  2.     struct Node *x = y->right;
  3.     y->right = x->left;
  4.     x->left = y;
  5.     y->height = std::max(getHeight(y->left), getHeight(y->right)) +1;
  6.     x->height = std::max(getHeight(x->left), getHeight(x->right)) +1;
  7.     return x;
  8. }

左右失衡如下图,这种情况需要先将x按照右右失衡情况处理,转换为左左失衡,然后按照左左失衡处理:


第一步处理完后,如下图:

之后就按照左左失衡处理就行了,代码奉上:

点击(此处)折叠或打开

  1. struct Node *avltree::lr_rotate(struct Node *y){
  2.     struct Node *x = y->left;
  3.     y->left = rr_rotate(x);
  4.     return ll_rotate(y);
  5. }

右左失衡如下图,这种情况需要先将x按照左左失衡情况处理,转换为右右失衡,然后按照右右失衡处理::


第一步调整后的结果如下图:


之后就按照右右失衡处理就行了,代码奉上:



点击(此处)折叠或打开

  1. struct Node *avltree::rl_rotate(struct Node *y){
  2.     struct Node *x = y->right;
  3.     y->right = ll_rotate(x);
  4.     return rr_rotate(y);
  5. }

接下来奉上整个插入代码:


点击(此处)折叠或打开

  1. struct Node *avltree::insert(int k, struct Node *node){
  2.     if(node == NULL) return (new struct Node(k));
  3.     if(k < node->val) node->left=insert(k, node->left);
  4.     else if( k > node->val) node->right=insert(k, node->right);
  5.     else return node;
  6.     node->height = std::max(getHeight(node->right), getHeight(node->left)) + 1;
  7.     int balance = isBalance(node);
  8.     if(balance > 1 && isBalance(node->left)>0) return ll_rotate(node);
  9.     if(balance > 1 && isBalance(node->left)<0) return lr_rotate(node);
  10.     if(balance < -1 && isBalance(node->right) > 0) return rl_rotate(node);
  11.     if(balance < -1 && isBalance(node->right) < 0) return rr_rotate(node);
  12.     return node;
  13. }
  14. void avltree::insert(int k){
  15.     root->left = insert(k, root->left);
  16. }

删除的话,跟插入是非常类似的,直接上代码了~


点击(此处)折叠或打开

  1. struct Node *avltree::delNode(int k, struct Node *node){
  2.     if(node==NULL) return NULL;
  3.     if(k < node->val) node->left = delNode(k, node->left);
  4.     else if(k > node->val) node->right = delNode(k, node->right);
  5.     else{
  6.         if(node->left && node->right){
  7.             struct Node *x = node->right;
  8.             while(x->left) x = x->left;
  9.             node->val = x->val;
  10.             node->right = delNode(x->val, node->right);
  11.         }else{
  12.             struct Node *p = node;
  13.             node = node->left?node->left:node->right;
  14.             delete p, p = NULL;
  15.             if(node == NULL) return NULL;
  16.         }
  17.     }
  18.     node->height = std::max(getHeight(node->right), getHeight(node->left)) + 1;
  19.     int balance = isBalance(node);
  20.     if(balance > 1 && isBalance(node->left)>0) return ll_rotate(node);
  21.     if(balance > 1 && isBalance(node->left)<0) return lr_rotate(node);
  22.     if(balance < -1 && isBalance(node->right) > 0) return rl_rotate(node);
  23.     if(balance < -1 && isBalance(node->right) < 0) return rr_rotate(node);
  24.     return node;
  25. }
  26. void avltree::delNode(int k){
  27.     root->left = delNode(k, root->left);
  28. }

整个类的代码如下:



点击(此处)折叠或打开

  1. #ifndef AVLTREE_H
  2. #define AVLTREE_H
  3. #include <iostream>
  4. struct Node{
  5.     struct Node *left;
  6.     struct Node *right;
  7.     int val;
  8.     int height;
  9.     Node(int x):val(x), height(1), left(NULL), right(NULL){}
  10. };

  11. class avltree
  12. {
  13. public:
  14.     avltree();
  15.     int isBalance(struct Node *node);
  16.     int getHeight(struct Node *node);
  17.     struct Node *ll_rotate(struct Node *y);
  18.     struct Node *rr_rotate(struct Node *y);
  19.     struct Node *lr_rotate(struct Node *y);
  20.     struct Node *rl_rotate(struct Node *y);
  21.     struct Node *insert(int k, struct Node *node);
  22.     void insert(int k);
  23.     struct Node *delNode(int k, struct Node *node);
  24.     void delNode(int k);
  25.     struct Node *root;
  26. };

  27. #endif // AVLTREE_H


点击(此处)折叠或打开

  1. avltree::avltree(){
  2.     root = new struct Node(0);
  3. }
  4. int avltree::isBalance(struct Node *node){
  5.     if(node == NULL) return 0;
  6.     return getHeight(node->left) - getHeight(node->right);
  7. }
  8. int avltree::getHeight(struct Node *node){
  9.     if(node == NULL) return 0;
  10.     return node->height;
  11. }
  12. struct Node *avltree::ll_rotate(struct Node *y){
  13.     struct Node *x = y->left;
  14.     y->left = x->right;
  15.     x->right = y;
  16.     y->height = std::max(getHeight(y->left), getHeight(y->right)) +1;
  17.     x->height = std::max(getHeight(x->left), getHeight(x->right)) +1;
  18.     return x;
  19. }
  20. struct Node *avltree::rr_rotate(struct Node *y){
  21.     struct Node *x = y->right;
  22.     y->right = x->left;
  23.     x->left = y;
  24.     y->height = std::max(getHeight(y->left), getHeight(y->right)) +1;
  25.     x->height = std::max(getHeight(x->left), getHeight(x->right)) +1;
  26.     return x;
  27. }
  28. struct Node *avltree::lr_rotate(struct Node *y){
  29.     struct Node *x = y->left;
  30.     y->left = rr_rotate(x);
  31.     return ll_rotate(y);
  32. }
  33. struct Node *avltree::rl_rotate(struct Node *y){
  34.     struct Node *x = y->right;
  35.     y->right = ll_rotate(x);
  36.     return rr_rotate(y);
  37. }
  38. struct Node *avltree::insert(int k, struct Node *node){
  39.     if(node == NULL) return (new struct Node(k));
  40.     if(k < node->val) node->left=insert(k, node->left);
  41.     else if( k > node->val) node->right=insert(k, node->right);
  42.     else return node;
  43.     node->height = std::max(getHeight(node->right), getHeight(node->left)) + 1;
  44.     int balance = isBalance(node);
  45.     if(balance > 1 && isBalance(node->left)>0) return ll_rotate(node);
  46.     if(balance > 1 && isBalance(node->left)<0) return lr_rotate(node);
  47.     if(balance < -1 && isBalance(node->right) > 0) return rl_rotate(node);
  48.     if(balance < -1 && isBalance(node->right) < 0) return rr_rotate(node);
  49.     return node;
  50. }
  51. void avltree::insert(int k){
  52.     root->left = insert(k, root->left);
  53. }
  54. struct Node *avltree::delNode(int k, struct Node *node){
  55.     if(node==NULL) return NULL;
  56.     if(k < node->val) node->left = delNode(k, node->left);
  57.     else if(k > node->val) node->right = delNode(k, node->right);
  58.     else{
  59.         if(node->left && node->right){
  60.             struct Node *x = node->right;
  61.             while(x->left) x = x->left;
  62.             node->val = x->val;
  63.             node->right = delNode(x->val, node->right);
  64.         }else{
  65.             struct Node *p = node;
  66.             node = node->left?node->left:node->right;
  67.             delete p, p = NULL;
  68.             if(node == NULL) return NULL;
  69.         }
  70.     }
  71.     node->height = std::max(getHeight(node->right), getHeight(node->left)) + 1;
  72.     int balance = isBalance(node);
  73.     if(balance > 1 && isBalance(node->left)>0) return ll_rotate(node);
  74.     if(balance > 1 && isBalance(node->left)<0) return lr_rotate(node);
  75.     if(balance < -1 && isBalance(node->right) > 0) return rl_rotate(node);
  76.     if(balance < -1 && isBalance(node->right) < 0) return rr_rotate(node);
  77.     return node;
  78. }
  79. void avltree::delNode(int k){
  80.     root->left = delNode(k, root->left);
  81. }

如果各位看官发现有问题,欢迎拍砖探讨~

阅读(81) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册