[DS] AVL树 和 伸展树

news/2024/7/2 20:25:49

= =AVL树和伸展树的代码实现

//ConstVar.h常数定义
#ifndef MYOOP_CONSTVAR_H
#define MYOOP_CONSTVAR_H
const int PREORDER = 1;
const int INORDER = 2;
const int POSTORDER = 3;
#endif //MYOOP_CONSTVAR_H

//AVL树

#ifndef MYOOP_AVLTREE_H
#define MYOOP_AVLTREE_H

#include <iostream>
#include "ConstVar.h"
#include <algorithm>
using std::max;

template <class T>
class AVLNode{
public:
    T element;
    int height;
    AVLNode* parent;
    AVLNode* left;
    AVLNode* right;
    AVLNode(const T& element,AVLNode* parent ){
        height = 0;
        this->element = element;
        this->parent = parent;
        left = right = nullptr;
    }
};

template <class T>
class AVLTree{
private:
    AVLNode<T> * root;
public:
    AVLTree();
    ~AVLTree();
    AVLTree(const AVLTree & tree);
    AVLNode<T>* getRoot();
    AVLNode<T>* find(const T& value);
    void insert(const T& value);
    void remove(const T& value);
    void printTree(const int & code);
    void makeEmpty();
private:
    int Height(const AVLNode<T>* tree) const ;
    void leftRotation(AVLNode<T>* aboveNode);
    void rightRotation(AVLNode<T>* aboveNode);
    AVLNode<T> *findMin(AVLNode<T>* tree) const ;
    void insert(const T& value, AVLNode<T>* parent);
    void remove(const T &value,AVLNode<T>* &tree);
    void replace(AVLNode<T>* ori,AVLNode<T>* to);
    void inorder(const AVLNode<T>* tree) const ;
    void preorder(const AVLNode<T>* tree) const ;
    void postorder(const AVLNode<T>* tree) const ;
    void makeEmpty(AVLNode<T>* &tree);
};

template <class T>
AVLTree<T>::AVLTree() {
    root = nullptr;
}
template <class T>
AVLTree<T>::~AVLTree() {
    makeEmpty();
}
template <class T>
AVLTree<T>::AVLTree(const AVLTree<T> &tree) {
    this->root = tree.root;
}
template <class T>
AVLNode<T>* AVLTree<T>::getRoot() {
    return root;
}
template <class T>
AVLNode<T>* AVLTree<T>::find(const T &value) {
    if(!this->root) return nullptr;
    AVLNode<T>* cur = this->root;
    while(cur != nullptr){
        if(cur->element == value) return cur;
        else if(value<cur->element){
            cur = cur->left;
        }else{
            cur = cur->right;
        }
    }
    return nullptr;
}
template <class T>
int AVLTree<T>::Height(const AVLNode<T>* tree)const {
    if(!tree) return -1;
    else return tree->height;
}
template <class T>
void AVLTree<T>::leftRotation(AVLNode<T> *aboveNode) {
    AVLNode<T>* child = aboveNode->right;
    if(child){
        aboveNode->right = child->left;
        if(child->left) child->left->parent = aboveNode;
        child->parent = aboveNode->parent;
        child->left = aboveNode;
    }
    if(!aboveNode->parent){
        root = child;
    }else if(aboveNode==aboveNode->parent->left)
        aboveNode->parent->left = child;
    else
        aboveNode->parent->right = child;
    aboveNode->parent = child;

    aboveNode->height = max(Height(aboveNode->left),Height(aboveNode->right))+1;
    if(child) child->height = max(Height(child->left),Height(child->right))+1;
}
template <class T>
void AVLTree<T>::rightRotation(AVLNode<T> *aboveNode) {
    AVLNode<T>* child = aboveNode->left;
    if(child){
        aboveNode->left = child->right;
        if(child->right) child->right->parent = aboveNode;
        child->parent = aboveNode->parent;
        child->right = aboveNode;
    }
    if(!aboveNode->parent){
        root = child;
    }else if(aboveNode==aboveNode->parent->left)
        aboveNode->parent->left = child;
    else
        aboveNode->parent->right = child;
    aboveNode->parent = child;

    aboveNode->height = max(Height(aboveNode->left),Height(aboveNode->right))+1;
    if(child) child->height = max(Height(child->left),Height(child->right))+1;
}
template <class T>
void AVLTree<T>::printTree(const int &code) {
    switch(code){
        case PREORDER:
            preorder(this->root);
            break;
        case INORDER:
            inorder(this->root);
            break;
        case POSTORDER:
            postorder(this->root);
            break;
        default:break;
    }
    std::cout<<std::endl;
}
template <class T>
void AVLTree<T>::preorder(const AVLNode<T> *tree) const {
    if(tree){
        std::cout<<tree->element<<' ';
        preorder(tree->left);
        preorder(tree->right);
    }
}
template <class T>
void AVLTree<T>::inorder(const AVLNode<T> *tree) const {
    if(tree){
        inorder(tree->left);
        std::cout<<tree->element<<' ';
        inorder(tree->right);
    }
}
template <class T>
void AVLTree<T>::postorder(const AVLNode<T> *tree) const {
    if(tree){
        postorder(tree->left);
        postorder(tree->right);
        std::cout<<tree->element<<' ';
    }
}
template <class T>
void AVLTree<T>::makeEmpty() {
    makeEmpty(root);
}
template <class T>
void AVLTree<T>::makeEmpty(AVLNode<T> *&tree) {
    if(!tree) return ;
    if(tree->left) makeEmpty(tree->left);
    if(tree->right) makeEmpty(tree->right);
    delete tree;
    tree = nullptr;
}
template <class T>
AVLNode<T>* AVLTree<T>::findMin(AVLNode<T> *tree) const {
    if(!tree) return nullptr;
    while(tree->left != nullptr) tree = tree->left;
    return tree;
}

template <class T>
void AVLTree<T>::insert(const T &value) {
    if(!root) root = new AVLNode<T>(value, nullptr);
    else insert(value,root);
}

template <class T>
void AVLTree<T>::insert(const T &value, AVLNode<T> *parent) {
    if(value < parent->element){
        if(parent->left){
            insert(value,parent->left);
        }else{
            parent->left = new AVLNode<T>(value,parent);
        }
        parent->height = max(Height(parent->left),Height(parent->right))+1;
        if(Height(parent->left)-Height(parent->right)==2){
            if(value<parent->left->element){
                //ll
                rightRotation(parent);
            }else{
                //lr
                leftRotation(parent->left);
                rightRotation(parent);
            }
        }
    }else if(value > parent->element){
        if(parent->right){
            insert(value,parent->right);
        }else{
            parent->right = new AVLNode<T>(value,parent);
        }
        parent->height = max(Height(parent->left),Height(parent->right))+1;
        if(Height(parent->right)-Height(parent->left)==2){
            if(value>parent->right->element){
                //rr
                leftRotation(parent);
            }else{
                //rl
                rightRotation(parent->right);
                leftRotation(parent);
            }
        }
    }else{
        //do nothing
    }

}
template <class T>
void AVLTree<T>::replace(AVLNode<T> *ori, AVLNode<T> *to) {
    if(ori->parent==nullptr)
        this->root = to;
    else if(ori == ori->parent->left)
        ori->parent->left = to;
    else
        ori->parent->right = to;
    if(to != nullptr) to->parent = ori->parent;
}
template <class T>
void AVLTree<T>::remove(const T &value) {
   remove(value,root);
}
template <class T>
void AVLTree<T>::remove(const T &value,AVLNode<T> *&tree) {
    if(!tree) return ;
    if(value<tree->element){
        remove(value,tree->left);
        if(Height(tree->right)-Height(tree->left)==2){
            if(Height(tree->right->right)>=Height(tree->right->left)){
                leftRotation(tree);
            }else{
                rightRotation(tree->right);
                leftRotation(tree);
            }
        }
    }else if(value>tree->element){
        remove(value,tree->right);
        if(Height(tree->left)-Height(tree->right)==2){
            if(Height(tree->left->left)>=Height(tree->left->right)){
                rightRotation(tree);
            }else{
                leftRotation(tree->left);
                rightRotation(tree);
            }
        }
    }else{
        if(tree->left!=nullptr && tree->right!= nullptr){
            AVLNode<T>* minnode = findMin(tree->right);
            tree->element = minnode->element;
            minnode->element = value;
            remove(value,tree->right);
            tree->height = max(Height(tree->left),Height(tree->right))+1;
        }else if(tree->left == nullptr){
            replace(tree,tree->right);
        }else if(tree->right == nullptr){
            replace(tree,tree->left);
        }
    }
    if(tree) tree->height = max(Height(tree->left),Height(tree->right))+1;
}


#endif //MYOOP_AVLTREE_H


//伸展树
#ifndef MYOOP_SPLAYTREE_H
#define MYOOP_SPLAYTREE_H

#include <iostream>
#include "ConstVar.h"
#include "AVLTree.h"

template <class T>
class SPTNode{
public:
    T element;
    SPTNode* parent;
    SPTNode* left;
    SPTNode* right;
    SPTNode(const T& element,SPTNode* parent ){
        this->element = element;
        this->parent = parent;
        left = right = nullptr;
    }
};

template <class T>
class SPTree{
private:
    SPTNode<T> * root;
public:
    SPTree();
    ~SPTree();
    SPTree(const SPTree & tree);
    SPTNode<T>* getRoot();
    SPTNode<T>* find(const T& value);
    void insert(const T& value);
    void remove(const T& value);
    void printTree(const int & code);
    void makeEmpty();
private:
    void leftRotation(SPTNode<T>* aboveNode);
    void rightRotation(SPTNode<T>* aboveNode);
    void splay(SPTNode<T>* node);
    SPTNode<T> *findMin(SPTNode<T>* tree) const ;
    void insert(const T& value, SPTNode<T>* parent);
    void remove(SPTNode<T>* &target);
    void replace(SPTNode<T>* ori,SPTNode<T>* to);
    void inorder(const SPTNode<T>* tree) const ;
    void preorder(const SPTNode<T>* tree) const ;
    void postorder(const SPTNode<T>* tree) const ;
    void makeEmpty(SPTNode<T>* &tree);
};
template <class T>
SPTree<T>::SPTree() { 
    root = nullptr;
}
template <class T>
SPTree<T>::~SPTree() {
    makeEmpty();
}
template <class T>
SPTree<T>::SPTree(const SPTree & tree) {
    this->root = tree.root;
}
template <class T>
SPTNode<T>* SPTree<T>::getRoot() {
    return this->root;
}
template <class T>
void SPTree<T>::leftRotation(SPTNode<T> *aboveNode) {
    SPTNode<T>* child = aboveNode->right;
    if(child){
        aboveNode->right = child->left;
        if(child->left) child->left->parent = aboveNode;
        child->parent = aboveNode->parent;
        child->left = aboveNode;
    }
    if(!aboveNode->parent){
        root = child;
    }else if(aboveNode==aboveNode->parent->left)
        aboveNode->parent->left = child;
    else
        aboveNode->parent->right = child;
    aboveNode->parent = child;
}
template <class T>
void SPTree<T>::rightRotation(SPTNode<T> *aboveNode) {
    SPTNode<T>* child = aboveNode->left;
    if(child){
        aboveNode->left = child->right;
        if(child->right) child->right->parent = aboveNode;
        child->parent = aboveNode->parent;
        child->right = aboveNode;
    }
    if(!aboveNode->parent){
        root = child;
    }else if(aboveNode==aboveNode->parent->left)
        aboveNode->parent->left = child;
    else
        aboveNode->parent->right = child;
    aboveNode->parent = child;
}
template <class T>
void SPTree<T>::splay(SPTNode<T> *node) {
    if(!node) return ;
    while(node->parent){
        if(!node->parent->parent){
            if(node==node->parent->left){
                rightRotation(node->parent);
            }else{
                leftRotation(node->parent);
            }
        }else{
            if(node==node->parent->left&&node->parent==node->parent->parent->left){
                rightRotation(node->parent->parent);
                rightRotation(node->parent);
            }else if(node==node->parent->right && node->parent==node->parent->parent->right){
                leftRotation(node->parent->parent);
                leftRotation(node->parent);
            }else if(node==node->parent->right && node->parent==node->parent->parent->left){
                leftRotation(node->parent);
                rightRotation(node->parent);
            }else{
                rightRotation(node->parent);
                leftRotation(node->parent);
            }
        }
    }
}
template <class T>
SPTNode<T>* SPTree<T>::find(const T &value) {
    if(!root) return nullptr;
    SPTNode<T>* cur = root;
    while(cur!=nullptr){
        if(value<cur->element){
            cur = cur->left;
        }else if(value>cur->element){
            cur = cur->right;
        }else{
            break;
        }
    }
    if(cur) splay(cur);
    return root;
}
template <class T>
SPTNode<T>* SPTree<T>::findMin(SPTNode<T> *tree) const {
    if(!tree) return nullptr;
    while(tree->left) tree = tree->left;
    return tree;
}
template <class T>
void SPTree<T>::insert(const T &value) {
    if(!this->root){
        this->root = new SPTNode<T>(value, nullptr);
    }else{
        insert(value,this->root);
    }
}
template <class T>
void SPTree<T>::insert(const T &value, SPTNode<T> *parent) {
    SPTNode<T>* newOne = nullptr;
    if(value<parent->element){
        if(parent->left == nullptr){
            newOne = parent->left = new SPTNode<T>(value,parent);
        }else{
            insert(value,parent->left);
        }
    }else if(value>parent->element){
        if(parent->right == nullptr){
            newOne = parent->right = new SPTNode<T>(value,parent);
        }else{
            insert(value,parent->right);
        }
    }else{
        return ;
    }
    splay(newOne);
}
template <class T>
void SPTree<T>::replace(SPTNode<T> *ori, SPTNode<T> *to) {
    if(ori->parent==nullptr)
        this->root = to;
    else if(ori == ori->parent->left)
        ori->parent->left = to;
    else
        ori->parent->right = to;
    if(to != nullptr) to->parent = ori->parent;
}
template <class T>
void SPTree<T>::remove(const T &value) {
    if(!this->root) return ;
    SPTNode<T>* cur = this->root;
    while(cur != nullptr){
        if(cur->element == value) break;
        else if(value<cur->element){
            cur = cur->left;
        }else{
            cur = cur->right;
        }
    }
    if(cur) {
      splay(cur);
      remove(cur);
    }
      
}
template <class T>
void SPTree<T>::remove(SPTNode<T> *&target) {
    if(!target->left) replace(target,target->right);
    else if(!target->right) replace(target,target->left);
    else{
        SPTNode<T>* child = findMin(target->right);
        if(child->parent != target){
            replace(child,child->right);
            child->right = target->right;
            child->right->parent = child;
        }
        replace(target,child);
        child->left = target->left;
        child->left->parent = child;
    }
    delete target;
}


template <class T>
void SPTree<T>::printTree(const int &code) {
    switch(code){
        case PREORDER:
            preorder(this->root);
            break;
        case INORDER:
            inorder(this->root);
            break;
        case POSTORDER:
            postorder(this->root);
            break;
        default:break;
    }
    std::cout<<std::endl;
}
template <class T>
void SPTree<T>::inorder(const SPTNode<T> *tree) const {
    if(tree){
        inorder(tree->left);
        std::cout<<tree->element<<' ';
        inorder(tree->right);
    }
}
template <class T>
void SPTree<T>::preorder(const SPTNode<T> *tree) const {
    if(tree){
        std::cout<<tree->element<<' ';
        preorder(tree->left);
        preorder(tree->right);
    }
}
template <class T>
void SPTree<T>::postorder(const SPTNode<T> *tree) const {
    if(tree){
        postorder(tree->left);
        postorder(tree->right);
        std::cout<<tree->element<<' ';
    }
}
template <class T>
void SPTree<T>::makeEmpty() {
    makeEmpty(root);
}
template <class T>
void SPTree<T>::makeEmpty(SPTNode<T> *&tree) {
    if(!tree) return;
    if(tree->left)makeEmpty(tree->left);
    if(tree->right)makeEmpty(tree->right);
    delete tree;
    tree = nullptr;
}

#endif //MYOOP_SPLAYTREE_H

http://www.niftyadmin.cn/n/965131.html

相关文章

static 修饰 函数内的局部变量

static 修饰 函数内的局部变量

void incre(); int x 3; void main() {int i;for (i 1; i < x; i) //这里的x是3&#xff0c;是不会变的。incre(); } void incre() {static int x 1; //这里对x的赋值只会执行一次。x * x 1;//第一次x1参加运算&#xff0c;第二次x2参加运算。printf("%d", …
阅读更多...
adb forward端口转发

adb forward端口转发

2019独角兽企业重金招聘Python工程师标准>>> 命令&#xff1a;adb forward tcp:6100 tcp:7100 // PC上所有6100端口通信数据将被重定向到手机端7100端口server上或者adb forward tcp:6100 local:logd // PC上所有6100端口通信数据将被重定向到手机端UNIX类型socket上…
阅读更多...
函数的重载，覆盖和隐藏的区别

函数的重载，覆盖和隐藏的区别

函数的重载&#xff0c;覆盖和隐藏的区别 1&#xff09;函数重载&#xff0c;相同的函数名&#xff0c;但是参数的类型&#xff0c;参数的个数&#xff0c;参数的顺序不同的&#xff0c;称为函数重载。注意&#xff0c;仅返回值不同的不算是函数重载&#xff0c;主要应用于实现…
阅读更多...
迁移项目 C++ Visual Studio

迁移项目 C++ Visual Studio

使用场景 我记得以前大学的时候经常下载别人的代码&#xff0c;然后弄到自己的电脑上来跑&#xff0c;这就是迁移项目啊。 又或者自己写的代码要在不同的电脑上面做开发&#xff0c;做测试等&#xff0c;也需要迁移项目。 像我今天就迁移了一个项目。 注意的问题 1.迁移之前…
阅读更多...
C++ static的作用 解释+代码

C++ static的作用 解释+代码

static的作用 ①.隐藏&#xff1a;static可以用作函数和变量的前面可表示隐藏。对于函数来讲&#xff0c;static的作用仅限于隐藏。 ②.周期不同&#xff1a;存储在静态数据区的变量会在程序刚开始运行时就完成初始化&#xff0c;也是唯一的一次初始化。共有两种变量存储在静态…
阅读更多...
C++ 回调函数 我给你分析清楚地址之间的关系

C++ 回调函数 我给你分析清楚地址之间的关系

函数指针 首先要知道函数指针是个啥&#xff0c;才好理解回调函数。 int func1(int a, int b) {return a b; } void test01() {//定义函数类型 typedef int(my_func)(int, int);//定义函数指针 cout << func1 << endl; //002E1604my_func* pFunc func1; //…
阅读更多...
redis使用命令拾遗

redis使用命令拾遗

2019独角兽企业重金招聘Python工程师标准>>> redis设置过期时间&#xff1a; set key value expire key 1200 返回1表示成功&#xff0c;返回0表示键不存在或者设置失败 ttl key 查看key的过期时间&#xff0c;键不存在返回-2&#xff0c;没有过期时间为-1 …
阅读更多...
计算大数的阶乘 代码详细解释

计算大数的阶乘 代码详细解释

#include <stdio.h> #include<stdlib.h>//要使用malloc是要包含此头文件&#xff0c;动态内存分配 #include<math.h> //因为要求的n比较大&#xff0c;所以正常的整数可能是存储不下的。 //所以需要 使用别的方法。 //这里使用的方法就是建立动态数组&#x…
阅读更多...
最新文章

Copyright @ 2022~2023