前两天种了一堆树：二叉树、AVL树、红黑树、B树、森林与树
但其实里面有不少伪代码的，所以我觉得还是自己动手写出来会好一些。
文章目录
- 在原始数据上创建AVL树
- LL （右旋）：在左叶的左侧插入数据
- RR（左旋）：在右子叶的右侧插入数据
- LR（左右旋）：在左叶节点的右侧插入数据
- RL（右左旋）：在右叶节点的左侧插入数据
- 新节点的插入
- 现有节点的删除
在原始数据上创建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);
}
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);
}
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);
}
LR（左右旋）：在左叶节点的右侧插入数据
我们将这种情况抽象出来，得到下图：
我们需要对节点y进行平衡的维护。步骤如下图所示：
第三个图里面x和z的位置换一下。
接下来如果有心人可以自己动手尝试一下了，下面的代码是我的尝试：
TreeNode* LR(TreeNode* root) {
root = RR(root);
root = LL(root);
return root;
}
//简单明了啊
RL（右左旋）：在右叶节点的左侧插入数据
我们将这种情况抽象出来，得到下图：
我们需要对节点y进行平衡的维护。步骤如下图所示：
第二个图中y的左孩子为T1，第三个图中x和z反了。
（被水印遮住的部分为：T1，T2，T3，T4）
TreeNode* RL(TreeNode* root) {
root = LL(root);
root = RR(root);
return root;
}
//简单明了啊
新节点的插入
木有图，各位自行脑补，自行实现。
以下是我的尝试：
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);
}
晕啊，调试调了半小时。。。
现有节点的删除
各位可以手动去写一下代码了，有前面的铺垫应该难度不大，我也去写一写。
我也是醉了，代码中有注释，那个指针，还删不掉了，真的是生命力顽强啊。。。。。
就那个指针，卡了我十分钟。。。
看来需要狠下心来去使用智能指针了。
//删除节点
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);
}
还有啥需要实现的吗？目前想不起来了哈哈。
下一篇咱一起来写个红黑树试试吧。
如果觉得好，阔以点赞关注收藏来一波哦。
如果觉得有哪些技术点不懂，可以参考开头那篇博客链接，那篇里面我把技术点讲的比较全，不过那篇代码比较缺失而已。
