Chinaunix首页 | 论坛 | 博客

猫尾八

首页　| 　博文目录　| 　关于我

StolennnXB

  • 博客访问： 1879341
  • 博文数量： 184
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 2388
  • 用 户 组： 普通用户
  • 注册时间： 2016-12-21 22:26
个人简介

90后空巢老码农

文章分类

全部博文（184）

文章存档

2021年（26）

2020年（56）

2019年（54）

2018年（47）

2017年（1）

我的朋友
最近访客
推荐博文
相关博文
平衡二叉搜索树简介

分类： 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. };

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

  29. #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. }

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

阅读(51016) | 评论(0) | 转发(0) |
0

上一篇：浅析二叉树的遍历以及二叉查找树

下一篇：《Linux Shell 脚本攻略》小结

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6