Discussion Detail - 追梦算法网

paste
手搓AVL（待验证~）
Kaptree Acmer LV 7 SU @ 2022-9-1 2:22:31

version 1

#include<cstring>
#include<iostream>
#include<algorithm>

template<typename T>
class AvlNode {
public:
    T key;
    int height;
    AvlNode *left,*right;
    AvlNode(int key) {
        this->key = key;
        this->height = 0;
        this->left = this->right = NULL;
    }
    ~AvlNode() {

    }
};

template<typename T>
class AvlTree {
public:

    AvlNode<T> *root;

    AvlTree() {
        this->root = NULL;
    }

    //获取树结点的高度
    int GetHeight(AvlNode<T> *root) {
        if(root != NULL)
            return root->height;
        return 0;
    }

    //更新树结点的高度
    int MaxHeight(AvlNode<T> *root) {
        if(root == NULL) return 0;
        return std::max(GetHeight(root->left),GetHeight(root->right)) + 1;
    }

    //判断是否失去平衡
    bool Check_Balance(AvlNode<T> *a, AvlNode<T> *b) {
        return abs(GetHeight(a) - GetHeight(b)) == 2;
    }
    /*
    这部分完善AVL的左旋、右旋、左右旋、右左旋
    */
    //简称为LL旋转（LL的含义是左子树的左子树插入新结点）
    AvlNode<T>* LeftLeftRotate(AvlNode<T> *root) {
        AvlNode<T> *lchild = root->left;//记录一下左子树根结点
        root->left = lchild->right;//将左子树的右子树变为根的左子树
        lchild->right = root;//将左子树的根变为整个子树的根，然后让其右子树指向之前的根

        //更新一下当前子树的根结点的高height
        lchild->height = MaxHeight(lchild);
        //更新一下被旋下去的结点，即当前子树的根的右子树结点的高height
        root->height = MaxHeight(root);

        return lchild;//返回子树旋转后的新的根
    }

    //简称为RR旋转（RR的含义是右子树的右子树插入新结点）
    AvlNode<T>* RightRightRotate(AvlNode<T> *root) {
        AvlNode<T> *rchild = root->right;
        root->right = rchild->left;
        rchild->left = root;

        rchild->height = MaxHeight(rchild);
        root->height = MaxHeight(root);

        return rchild;
    }

    AvlNode<T>* LeftRightRotate(AvlNode<T> *root) {
        root->left = RightRightRotate(root->left);//先对左子树进行进行RR旋转
        root = LeftLeftRotate(root);//然后对根节点进行LL旋转
        return root;
    }

    AvlNode<T>* RightLeftRotate(AvlNode<T> *root) {
        root->right = LeftLeftRotate(root->right);//先对右子树进行进行LL旋转
        root = RightRightRotate(root);//然后对根节点进行LL旋转
        return root;
    }

    //在AVL树中查找元素值为value的结点
    AvlNode<T>* ValueFind(AvlNode<T> *root,T value) {
        while(root != NULL && root->key != value) {
            if(root->key > value) root = root->left;//在左子树
            else root = root->right;//在右子树
        }
        return root;//没找到的话会返回NULL
    }

    AvlNode<T>* MinNode(AvlNode<T> *root) {
        if(root == NULL) return NULL;//特判一下空树的情况
        if(root->left == NULL) return root;
        return MinNode(root->left);
    }

    AvlNode<T>* MaxNode(AvlNode<T> *root) {
        if(root == NULL) return NULL;//特判一下空树的情况
        if(root->right == NULL) return root;
        return MaxNode(root->right);
    }

    //在AVL树中插入元素值为T的结点
    AvlNode<T>* InsetNode(AvlNode<T> *root,T value) {
        if(root == NULL) {
            root = new AvlNode<T>(value);
        } else if(root->key > value) {//插入左子树
            root->left = InsetNode(root->left,value);
            if(Check_Balance(root->left,root->right)) {//插入左子树后发现失去平衡
                if(value < root->left->key) //因为插入结点左子树的左子树上，所以进行LL旋转
                    root = LeftLeftRotate(root);
                else //插入结点在左子树的右子树上，所以LR旋转
                    root = LeftRightRotate(root);
            }
        } else {//插入右子树
            root->right = InsetNode(root->right,value);
            if(Check_Balance(root->right,root->left)) {//插入右子树后发现失去平衡
                if(value < root->right->key)//因为插入结点右子树的左子树上，所以进行RL旋转
                    root = RightLeftRotate(root);
                else //因为插入结点右子树的右子树上，所以进行RR旋转
                    root = RightRightRotate(root);
            }
        }
        root->height = MaxHeight(root);//计算结点高度
        return root;
    }

    //删除结点
    AvlNode<T>* DeleteNode(AvlNode<T> *root, AvlNode<T> *node) {
        if(root == NULL) return NULL;
        if(root->key == node->key) { //找到了删除的结点
            if(root->left != NULL && root->right != NULL) {
                //如果删除的结点的左树和右子树都不为空
                if(GetHeight(root->left) > GetHeight(root->right)) {
                    //如果左子树比右子树高的话，分三步进行
                    //一、找到当前结点的左子树的最大值结点
                    AvlNode<T> *max_node = MaxNode(root->left);
                    //二、将这个左子树的最大值赋给当前的根节点
                    root->key = max_node->key;
                    //三、删除左子树的最大值的结点（因为这个结点一定是只有左子树或者没有左子树的情况）
                    root->left = DeleteNode(root->left,max_node);
                } else {
                    //右子树和左子树更高或者相等,同样分三步
                    //一、找到当前结点的右子树上的最小值结点
                    AvlNode<T> *min_node = MinNode(root->right);
                    //二、将这个右子树的最小值赋给当前的根节点
                    root->key = min_node->key;
                    //三、删除右子树的最小值结点（和上面同理，一定是一个只有右子树或者没有右子树的情况）
                    root->right = DeleteNode(root->right,min_node);
                }
            } else {//左右子树都为空，或者是左子树为空，或者是右子树为空
                AvlNode<T> *tmp = root;//记录下删除的结点
                if(root->left == NULL) //如果左子树为空，那么就由右子树继承（当然右子树也可能是一个空树）
                    root = root->right;
                else //否则左子树继承
                    root = root->left;
                delete tmp;
            }
        }
        else if(root->key > node->key) {//删除的结点在左节点
            root->left = DeleteNode(root->left,node);
            if(Check_Balance(root->right,root->left)) {//右子树可能会失衡
                AvlNode<T> *TempRightNode = root->right;
                if(GetHeight(TempRightNode->left) > GetHeight(TempRightNode->right))
                    root = RightLeftRotate(root);//RR旋
                else
                    root = RightRightRotate(root);//RL旋
            }
        } else {//删除的结点在右子树
            root->right = DeleteNode(root->right,node);
            if(Check_Balance(root->left,root->right)) {//左子树可能会发生失衡
                AvlNode<T> *TempLeftNode = root->left;
                if(GetHeight(TempLeftNode->left) > GetHeight(TempLeftNode->right))
                    root = LeftLeftRotate(root);//LL旋
                else
                    root = LeftRightRotate(root);//LR旋
            }
        }
        if(root)
            root->height = MaxHeight(root);
        return root;
    }


    //先序遍历
    void PreOrder(AvlNode<T> *root) {
        if(root == NULL) return;
        std::cout<<root->key<<"->";
        PreOrder(root->left);
        PreOrder(root->right);
    }
    //中序遍历
    void InOrder(AvlNode<T> *root) {
        if(root == NULL) return;
        InOrder(root->left);
        std::cout<<root->key<<"->";
        InOrder(root->right);
    }
    //后序遍历
    void PostOrder(AvlNode<T> *root) {
        if(root == NULL) return;
        PostOrder(root->left);
        PostOrder(root->right);
        std::cout<<root->key<<"->";
    }


};

int main()
{

    AvlTree<int> * Tree = new AvlTree<int>();
//	AvlNode<int> * root = Tree->root;
    int n = 8;
    for(int i = 1;i <= n; ++i) {
        Tree->root = Tree->InsetNode(Tree->root,i);
        std::cout<<"-----------"<<std::endl;
        std::cout<<"先序遍历为："<<std::endl;
        Tree->PreOrder(Tree->root);
        std::cout<<"\n中序遍历为："<<std::endl;
        Tree->InOrder(Tree->root);
        std::cout<<std::endl;
    }
    std::cout<<"hello"<<std::endl;
    AvlNode<int> *p = Tree->ValueFind(Tree->root,5);
    Tree->DeleteNode(Tree->root,p);
    std::cout<<"-----------"<<std::endl;
    std::cout<<"先序遍历为："<<std::endl;
    Tree->PreOrder(Tree->root);
    std::cout<<"\n中序遍历为："<<std::endl;
    Tree->InOrder(Tree->root);

    return 0;
}

version 2

#include<cstring>
#include<iostream>
#include<algorithm>

template<typename T>
class AvlNode {
public:
    T key;
    int height;
    AvlNode *left,*right;
    AvlNode(int key) {
        this->key = key;
        this->height = 0;
        this->left = this->right = NULL;
    }
    ~AvlNode() {

    }
};

template<typename T>
class AvlTree {
public:

    AvlNode<T> *root;

    AvlTree() {
        this->root = NULL;
    }

    //获取树结点的高度
    int GetHeight(AvlNode<T> *root);

    //更新树结点的高度
    int MaxHeight(AvlNode<T> *root);

    //判断是否失去平衡，失去平衡返回true，否则返回false
    bool Check_Balance(AvlNode<T> *a, AvlNode<T> *b);

    //简称为LL旋转（LL的含义是左子树的左子树插入新结点）
    AvlNode<T>* LeftLeftRotate(AvlNode<T> *root);

    //简称为RR旋转（RR的含义是右子树的右子树插入新结点）
    AvlNode<T>* RightRightRotate(AvlNode<T> *root);

    //简称为LR旋转（LR的含义是左子树的右子树插入新节点）
    AvlNode<T>* LeftRightRotate(AvlNode<T> *root);

    //简称为RL旋转（RL的含义是右子树的左子树插入新节点）
    AvlNode<T>* RightLeftRotate(AvlNode<T> *root);

    //在AVL树中查找元素值为value的结点
    AvlNode<T>* ValueFind(AvlNode<T> *root,T value);

    //找到AVL树中元素值最小的结点，即树的最左边
    AvlNode<T>* MinNode(AvlNode<T> *root);

    //找到AVL树中元素值最大的结点，即树的最右边
    AvlNode<T>* MaxNode(AvlNode<T> *root);

    //在AVL树中插入元素值为T的结点
    AvlNode<T>* InsetNode(AvlNode<T> *root,T value);

    //删除结点
    AvlNode<T>* DeleteNode(AvlNode<T> *root, AvlNode<T> *node);

    //先序遍历
    void PreOrder(AvlNode<T> *root) {
        if(root == NULL) return;
        std::cout<<root->key<<"->";
        PreOrder(root->left);
        PreOrder(root->right);
    }
    //中序遍历
    void InOrder(AvlNode<T> *root) {
        if(root == NULL) return;
        InOrder(root->left);
        std::cout<<root->key<<"->";
        InOrder(root->right);
    }
    //后序遍历
    void PostOrder(AvlNode<T> *root) {
        if(root == NULL) return;
        PostOrder(root->left);
        PostOrder(root->right);
        std::cout<<root->key<<"->";
    }
};

template<typename T>
int AvlTree<T>::GetHeight(AvlNode<T> *root) {
    if(root != NULL)
        return root->height;
    return 0;
}

template<typename T>
int AvlTree<T>::MaxHeight(AvlNode<T> *root) {
    if(root == NULL) return 0;
    return std::max(GetHeight(root->left),GetHeight(root->right)) + 1;
}

template<typename T>
bool AvlTree<T>::Check_Balance(AvlNode<T> *a, AvlNode<T> *b) {
    return abs(GetHeight(a) - GetHeight(b)) == 2;
}

template<typename T>
AvlNode<T>* AvlTree<T>::LeftLeftRotate(AvlNode<T> *root) {
    AvlNode<T> *lchild = root->left;//记录一下左子树根结点
    root->left = lchild->right;//将左子树的右子树变为根的左子树
    lchild->right = root;//将左子树的根变为整个子树的根，然后让其右子树指向之前的根

    //更新一下当前子树的根结点的高height
    lchild->height = MaxHeight(lchild);
    //更新一下被旋下去的结点，即当前子树的根的右子树结点的高height
    root->height = MaxHeight(root);

    return lchild;//返回子树旋转后的新的根
}
template<typename T>
AvlNode<T>* AvlTree<T>::RightRightRotate(AvlNode<T> *root) {
    AvlNode<T> *rchild = root->right;
    root->right = rchild->left;
    rchild->left = root;

    rchild->height = MaxHeight(rchild);
    root->height = MaxHeight(root);

    return rchild;
}

template<typename T>
AvlNode<T>* AvlTree<T>::LeftRightRotate(AvlNode<T> *root) {
    root->left = RightRightRotate(root->left);//先对左子树进行进行RR旋转
    root = LeftLeftRotate(root);//然后对根节点进行LL旋转
    return root;
}

template<typename T>
AvlNode<T>* AvlTree<T>::RightLeftRotate(AvlNode<T> *root) {
    root->right = LeftLeftRotate(root->right);//先对右子树进行进行LL旋转
    root = RightRightRotate(root);//然后对根节点进行LL旋转
    return root;
}

template<typename T>
AvlNode<T>* AvlTree<T>::ValueFind(AvlNode<T> *root,T value) {
    //如果当前走到了空结点或者找到了value值的结点都会退出，前者说明找不到
    while(root != NULL && root->key != value) {
        if(root->key > value)
            root = root->left;//在左子树
        else
            root = root->right;//在右子树
    }
    return root;//没找到的话会返回NULL
}

template<typename T>
AvlNode<T>* AvlTree<T>::MinNode(AvlNode<T> *root) {
    if(root == NULL)
        return NULL;//特判一下空树的情况
    if(root->left == NULL) //当结点的左子树为空，说明找到了
        return root;
    return MinNode(root->left);
}

template<typename T>
AvlNode<T>* AvlTree<T>::MaxNode(AvlNode<T> *root) {
    if(root == NULL) //特判一下空树的情况
        return NULL;
    if(root->right == NULL) //当结点的右子树为空，说明找到了
        return root;
    return MaxNode(root->right);//递归往右子树查找
}


template<typename T>
AvlNode<T>* AvlTree<T>::InsetNode(AvlNode<T> *root,T value) {
    if(root == NULL) {
        root = new AvlNode<T>(value);
    } else if(root->key > value) {//插入左子树
        root->left = InsetNode(root->left,value);
        if(Check_Balance(root->left,root->right)) {//插入左子树后发现失去平衡
            if(value < root->left->key) //因为插入结点左子树的左子树上，所以进行LL旋转
                root = LeftLeftRotate(root);
            else //插入结点在左子树的右子树上，所以LR旋转
                root = LeftRightRotate(root);
        }
    } else {//插入右子树
        root->right = InsetNode(root->right,value);
        if(Check_Balance(root->right,root->left)) {//插入右子树后发现失去平衡
            if(value < root->right->key)//因为插入结点右子树的左子树上，所以进行RL旋转
                root = RightLeftRotate(root);
            else //因为插入结点右子树的右子树上，所以进行RR旋转
                root = RightRightRotate(root);
        }
    }
    root->height = MaxHeight(root);//计算结点高度
    return root;
}

template<typename T>
AvlNode<T>* AvlTree<T>::DeleteNode(AvlNode<T> *root, AvlNode<T> *node) {
    if(root == NULL) return NULL;
    if(root->key == node->key) { //找到了删除的结点
        if(root->left != NULL && root->right != NULL) {
            //如果删除的结点的左树和右子树都不为空
            if(GetHeight(root->left) > GetHeight(root->right)) {
                //如果左子树比右子树高的话，分三步进行
                //一、找到当前结点的左子树的最大值结点
                AvlNode<T> *max_node = MaxNode(root->left);
                //二、将这个左子树的最大值赋给当前的根节点
                root->key = max_node->key;
                //三、删除左子树的最大值的结点（因为这个结点一定是只有左子树或者没有左子树的情况）
                root->left = DeleteNode(root->left,max_node);
            } else {
                //右子树和左子树更高或者相等,同样分三步
                //一、找到当前结点的右子树上的最小值结点
                AvlNode<T> *min_node = MinNode(root->right);
                //二、将这个右子树的最小值赋给当前的根节点
                root->key = min_node->key;
                //三、删除右子树的最小值结点（和上面同理，一定是一个只有右子树或者没有右子树的情况）
                root->right = DeleteNode(root->right,min_node);
            }
        } else {//左右子树都为空，或者是左子树为空，或者是右子树为空
            AvlNode<T> *tmp = root;//记录下删除的结点
            if(root->left == NULL) //如果左子树为空，那么就由右子树继承（当然右子树也可能是一个空树）
                root = root->right;
            else //否则左子树继承
                root = root->left;
            delete tmp;
        }
    }
    else if(root->key > node->key) {//删除的结点在左节点
        root->left = DeleteNode(root->left,node);
        if(Check_Balance(root->right,root->left)) {//右子树可能会失衡
            AvlNode<T> *TempRightNode = root->right;
            if(GetHeight(TempRightNode->left) > GetHeight(TempRightNode->right))
                root = RightLeftRotate(root);//RR旋
            else
                root = RightRightRotate(root);//RL旋
        }
    } else {//删除的结点在右子树
        root->right = DeleteNode(root->right,node);
        if(Check_Balance(root->left,root->right)) {//左子树可能会发生失衡
            AvlNode<T> *TempLeftNode = root->left;
            if(GetHeight(TempLeftNode->left) > GetHeight(TempLeftNode->right))
                root = LeftLeftRotate(root);//LL旋
            else
                root = LeftRightRotate(root);//LR旋
        }
    }
    if(root)
        root->height = MaxHeight(root);
    return root;
}

int main()
{

    AvlTree<int> * Tree = new AvlTree<int>();
//	AvlNode<int> * root = Tree->root;
    int n = 8;
    for(int i = 1;i <= n; ++i) {
        Tree->root = Tree->InsetNode(Tree->root,i);
        std::cout<<"-----------"<<std::endl;
        std::cout<<"先序遍历为："<<std::endl;
        Tree->PreOrder(Tree->root);
        std::cout<<"\n中序遍历为："<<std::endl;
        Tree->InOrder(Tree->root);
        std::cout<<std::endl;
    }
    std::cout<<"hello"<<std::endl;
    AvlNode<int> *p = Tree->ValueFind(Tree->root,5);
    Tree->DeleteNode(Tree->root,p);
    std::cout<<"-----------"<<std::endl;
    std::cout<<"先序遍历为："<<std::endl;
    Tree->PreOrder(Tree->root);
    std::cout<<"\n中序遍历为："<<std::endl;
    Tree->InOrder(Tree->root);

    return 0;
}

No comments so far...

手搓AVL（待验证~）

version 1

version 2

0 comments

Status

Development

Support

手搓AVL（待验证~）

version 1

version 2

0 comments

Status

Development

Support

Don't have an account?

SIGN IN