跟我一起 自己种一颗 AVL树（平衡二叉搜索树）吧！
【摘要】
前两天种了一堆树：二叉树、AVL树、红黑树、B树、森林与树 但其实里面有不少伪代码的，所以我觉得还是自己动手写出来会好一些。
文章目录
在原始数据上创建AVL树LL （右旋）：在左叶的左侧插入数据RR（左旋）：在右子叶的右侧插入数据LR（左右旋）：在左叶节点的右侧插入数据RL（右左旋）：在右叶节点的左侧插入数据新节点的插入现有节点的删除
在原始数...
前两天种了一堆树：二叉树、AVL树、红黑树、B树、森林与树
但其实里面有不少伪代码的，所以我觉得还是自己动手写出来会好一些。
在原始数据上创建AVL树
我也看了些资料，大部分都是说“霸王硬上弓”，插入、旋转、插入、旋转···
我感觉这样挺繁琐的，创建一棵树就要不断的旋转，旋转，而且由于数据的无序性，每次插入都要去找插入点，也挺浪费时间的。
我的想法在种树的时候就明确表达了，不过那会儿太累了就没去实现：先对原始数据进行排序，然后再填充二叉搜索树，使用递归的方式。
接下来如果有心人可以自己动手尝试一下了，下面的代码是我的尝试：
#include<iostream>
#include<vector>
using namespace std;
class TreeNode {
public: int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} TreeNode() : val(0), left(NULL), right(NULL) {}
};
void createTree(vector<int>& vec, TreeNode* root, int begin, int end) { //如果只剩一个键 if (begin == end) { root->val = vec[begin]; return; } int mid_sz = (begin+end)/2; root->val = vec[mid_sz]; if (mid_sz - 1 >= begin) { root->left = new TreeNode(0); createTree(vec, root->left, begin, mid_sz - 1); } root->right = new TreeNode(0); createTree(vec, root->right,mid_sz + 1,end);
}
void PreOrderTraverse(TreeNode* root) { if (NULL == root) return; cout << root->val; PreOrderTraverse(root->left); PreOrderTraverse(root->right);
}
int main() { TreeNode* roott = new TreeNode(0); vector<int> vec = { 0,1,2,3,4,5,6,7}; createTree(vec,roott,0,vec.size()-1); PreOrderTraverse(roott);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
LL （右旋）：在左叶的左侧插入数据
接下来如果有心人可以自己动手尝试一下了，下面的代码是我的尝试：
//在左叶的左侧插入数据
TreeNode* LL(TreeNode* root) { TreeNode* x = root->left; //即将返回的节点是y的左子节点 TreeNode* temp = x->right; //先把y的右子节点取出来 x->right = root; //把y放进x的右子节点 root->left = temp; //把前面预存的放到y的左子节点 return x;
}
int main() { TreeNode* roott = new TreeNode(0); vector<int> vec = { 0,1,2,3,4,5,6,7}; createTree(vec,roott,0,vec.size()-1); roott = LL(roott); PreOrderTraverse(roott);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
RR（左旋）：在右子叶的右侧插入数据
接下来如果有心人可以自己动手尝试一下了，下面的代码是我的尝试：
TreeNode* RR(TreeNode* root) { TreeNode* x = root->right; //即将返回的节点是y的右子节点 TreeNode* temp = x->left; //先把x的左子节点取出来 x->left = root; //把y放进x的左子节点 root->right = temp; //把前面预存的放到y的右子节点 return x;
}
int main() { TreeNode* roott = new TreeNode(0); vector<int> vec = { 0,1,2,3,4,5,6,7}; createTree(vec,roott,0,vec.size()-1); roott = RR(roott); PreOrderTraverse(roott);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
LR（左右旋）：在左叶节点的右侧插入数据
我们将这种情况抽象出来，得到下图：
我们需要对节点y进行平衡的维护。步骤如下图所示：
第三个图里面x和z的位置换一下。
接下来如果有心人可以自己动手尝试一下了，下面的代码是我的尝试：
TreeNode* LR(TreeNode* root) { root = RR(root); root = LL(root); return root;
}
//简单明了啊
- 1
- 2
- 3
- 4
- 5
- 6
RL（右左旋）：在右叶节点的左侧插入数据
我们将这种情况抽象出来，得到下图：
我们需要对节点y进行平衡的维护。步骤如下图所示：
第二个图中y的左孩子为T1，第三个图中x和z反了。
（被水印遮住的部分为：T1，T2，T3，T4）
TreeNode* RL(TreeNode* root) { root = LL(root); root = RR(root); return root;
}
//简单明了啊
- 1
- 2
- 3
- 4
- 5
- 6
新节点的插入
木有图，各位自行脑补，自行实现。
以下是我的尝试：
TreeNode* Insert_Node(TreeNode* root, int val) { //先将节点插入 if (NULL == root) return new TreeNode(val); else { if (val < root->val) root->left = Insert_Node(root->left, val); else root->right = Insert_Node(root->right, val); } //计算平衡因子 int balanceFactor = getBalanceFactor(root); //判断是否该旋转，该如何旋转 if (balanceFactor > 1) { //左子树有事儿 balanceFactor = getBalanceFactor(root->left); if (balanceFactor == 1) //插左边了 return LL(root); else if (balanceFactor == -1) //插右边了 return RR(root); else { cout << "罕见故障" << endl; } } else if (balanceFactor < -1) { //右子树有事儿 balanceFactor = getBalanceFactor(root->right); if (balanceFactor == 1) //插左边了 return RL(root); else if(balanceFactor == -1) //插右边了 return RR(root); else { cout << "罕见故障" << endl; } } return root;
}
int main() { TreeNode* roott = new TreeNode(0); vector<int> vec = { 0,1,2,3,4,5,6,7}; createTree(vec,roott,0,vec.size()-1); roott = Insert_Node(roott,8); PreOrderTraverse(roott);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
晕啊，调试调了半小时。。。
现有节点的删除
各位可以手动去写一下代码了，有前面的铺垫应该难度不大，我也去写一写。
我也是醉了，代码中有注释，那个指针，还删不掉了，真的是生命力顽强啊。。。。。
就那个指针，卡了我十分钟。。。
看来需要狠下心来去使用智能指针了。
//删除节点
TreeNode* DelSerchNode(TreeNode* node, int e) { if (node == NULL) return NULL; TreeNode* retNode; if (e < node->val) { node->left = DelSerchNode(node->left, e); retNode = node; } else if (e > node->val) { node->right = DelSerchNode(node->right, e); retNode = node; } else { // 待删除节点左子树为空的情况 if (node->left == NULL) { TreeNode* rightNode = node->right; node->right = NULL; retNode = rightNode; } // 待删除节点右子树为空的情况 else if (node->right == NULL) { TreeNode* leftNode = node->left; node->left = NULL; retNode = leftNode; } else { // 待删除节点左右子树均不为空的情况 // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点 // 用这个节点顶替待删除节点的位置 TreeNode* temp = node; while (NULL != temp->left) { temp = temp->left; } node->val = temp->val; node->left = NULL; //temp = NULL; //这还删不掉了。。。。这指针还真是顽强 delete temp; retNode = node; } } if (retNode == NULL) return NULL; //计算平衡因子 int balanceFactor = getBalanceFactor(retNode); //判断是否该旋转，该如何旋转 if (balanceFactor > 1) { //左子树有事儿 balanceFactor = getBalanceFactor(retNode->left); if (balanceFactor == 1) //插左边了 return LL(retNode); else if (balanceFactor == -1) //插右边了 return RR(retNode); else { cout << "罕见故障" << endl; } } else if (balanceFactor < -1) { //右子树有事儿 balanceFactor = getBalanceFactor(retNode->right); if (balanceFactor == 1) //插左边了 return RL(retNode); else if (balanceFactor == -1) //插右边了 return RR(retNode); else { cout << "罕见故障" << endl; } } return retNode;
}
int main() { TreeNode* roott = new TreeNode(0); vector<int> vec = { 0,1,2,3,4,5,6,7}; createTree(vec,roott,0,vec.size()-1); roott = DelSerchNode(roott,5); PreOrderTraverse(roott);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
还有啥需要实现的吗？目前想不起来了哈哈。
下一篇咱一起来写个红黑树试试吧。
如果觉得好，阔以点赞关注收藏来一波哦。
如果觉得有哪些技术点不懂，可以参考开头那篇博客链接，那篇里面我把技术点讲的比较全，不过那篇代码比较缺失而已。
文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。
原文链接：lion-wu.blog.csdn.net/article/details/107312316
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件至：cloudbbs@huaweicloud.com进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容。
- 点赞
- 收藏
- 关注作者
评论（0）