跟我一起 自己种一颗 AVL树（平衡二叉搜索树）吧！

2020-08-26 11:22:28 浏览数 (1)

在原始数据上创建AVL树

我也看了些资料，大部分都是说“霸王硬上弓”，插入、旋转、插入、旋转··· 我感觉这样挺繁琐的，创建一棵树就要不断的旋转，旋转，而且由于数据的无序性，每次插入都要去找插入点，也挺浪费时间的。

我的想法在种树的时候就明确表达了，不过那会儿太累了就没去实现：先对原始数据进行排序，然后再填充二叉搜索树，使用递归的方式。

接下来如果有心人可以自己动手尝试一下了，下面的代码是我的尝试：

代码语言：javascript复制
#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 （右旋）：在左叶的左侧插入数据

接下来如果有心人可以自己动手尝试一下了，下面的代码是我的尝试：

代码语言：javascript复制
//在左叶的左侧插入数据
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（左旋）：在右子叶的右侧插入数据

接下来如果有心人可以自己动手尝试一下了，下面的代码是我的尝试：

代码语言：javascript复制
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的位置换一下。

接下来如果有心人可以自己动手尝试一下了，下面的代码是我的尝试：

代码语言：javascript复制
TreeNode* LR(TreeNode* root) {
    root = RR(root);
    root = LL(root);
    return root;
}
//简单明了啊

RL（右左旋）：在右叶节点的左侧插入数据

我们将这种情况抽象出来，得到下图：

我们需要对节点y进行平衡的维护。步骤如下图所示：

第二个图中y的左孩子为T1，第三个图中x和z反了。

（被水印遮住的部分为：T1，T2，T3，T4）

代码语言：javascript复制
TreeNode* RL(TreeNode* root) {
    root = LL(root);
    root = RR(root);
    return root;
}
//简单明了啊

新节点的插入

木有图，各位自行脑补，自行实现。

以下是我的尝试：

代码语言：javascript复制
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);
}

晕啊，调试调了半小时。。。

现有节点的删除

各位可以手动去写一下代码了，有前面的铺垫应该难度不大，我也去写一写。

我也是醉了，代码中有注释，那个指针，还删不掉了，真的是生命力顽强啊。。。。。

就那个指针，卡了我十分钟。。。 看来需要狠下心来去使用智能指针了。

代码语言：javascript复制
//删除节点
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);
}

还有啥需要实现的吗？目前想不起来了哈哈。

下一篇咱一起来写个红黑树试试吧。

t4

0 人点赞