说明

伸展树的出发点：
局部性原理:刚被访问的内容下次可能仍会被访问，查找次数多的内容可能下一次会被访问。
为了使整个查找时间更小，被查频率高的那些节点应当经常处于靠近树根的位置。

做法

每次对伸展树进行操作后，均会通过旋转的方法把被访问节点旋转到树根的位置。
将节点自底向上旋转，直至该节点成为树根为止。

代码 SplayTree.h

#pragma once

#include <algorithm>
#include <functional>
#include <initializer_list>
#include <queue>
#include <utility>
#include <optional>

namespace ds {
    template<typename T>
    class SplayTree;

    template<typename T>
    class SplayTreeNode {
    public:
        friend class SplayTree<T>;

    public:
        SplayTreeNode() = default;
        //默认指针是空
        explicit SplayTreeNode(const T& key) : key_(key) {}

        //构造函数固定写法，不许 常量引用 和 引用的引用
        SplayTreeNode(const SplayTreeNode&) = delete;
        SplayTreeNode(SplayTreeNode&&) = delete;
        ~SplayTreeNode() = default;
        SplayTreeNode& operator=(const SplayTreeNode&) = delete;
        SplayTreeNode& operator=(SplayTreeNode&&) = delete;


        T key_;

    private:
        SplayTreeNode* parent_{ nullptr };
        SplayTreeNode* left_{ nullptr };
        SplayTreeNode* right_{ nullptr };
    };

    template<typename T>
    class SplayTree {
    public:
        using callback_t = std::function<void(T&)>;//定义访问函数做参数

    public:
        SplayTree() = default;
        SplayTree(std::initializer_list<T> keys);

        //构造函数固定写法：禁止出现 常量的引用 引用的引用
        SplayTree(const SplayTree&) = delete;
        SplayTree(SplayTree&&) = delete;
        ~SplayTree();
        SplayTree& operator=(const SplayTree&) = delete;
        SplayTree& operator=(SplayTree&&) = delete;

        //访问函数
        void pre_order_traversal(callback_t callback);
        void in_order_traversal(callback_t callback);
        void post_order_traversal(callback_t callback);
        void level_order_traversal(callback_t callback);

        //功能函数
        void insert(const T& key);
        template<typename U>
        auto search(const U& key);
        auto minimum();
        auto maximum();
        int height();
        int size();
        void clear();

    private:

        //固定写法，helper内使用指针，方便递归实现
        void pre_order_traversal_helper(SplayTreeNode<T>* root, callback_t callback);
        void in_order_traversal_helper(SplayTreeNode<T>* root, callback_t callback);
        void post_order_traversal_helper(SplayTreeNode<T>* root, callback_t callback);
        void breadth_first_traversal_helper(SplayTreeNode<T>* root, callback_t callback);

        //
        void splay(SplayTreeNode<T>* root);
        void rotate_left(SplayTreeNode<T>* rotation_root);
        void rotate_right(SplayTreeNode<T>* rotation_root);


        template<typename U>
        SplayTreeNode<T>* search_helper(SplayTreeNode<T>* root, const U& key);
        SplayTreeNode<T>* minimum_helper(SplayTreeNode<T>* root);
        SplayTreeNode<T>* maximum_helper(SplayTreeNode<T>* root);
        int height_helper(const SplayTreeNode<T>* root);
        int size_helper(const SplayTreeNode<T>* root);
        void clear_helper(SplayTreeNode<T>* root);

        //唯一的 私有变量
        SplayTreeNode<T>* root_{ nullptr };
    };

    //可以这样初始化 SplayTree st({1,332,1,23,243,});
    template<typename T>
    SplayTree<T>::SplayTree(std::initializer_list<T> keys) {
        for (auto key : keys) {
            insert(key);
        }
    }

    template<typename T>
    SplayTree<T>::~SplayTree() {
        clear();
    }

    //固定写法，调用helper递归实现
    template<typename T>
    void SplayTree<T>::pre_order_traversal(SplayTree::callback_t callback) {
        pre_order_traversal_helper(root_, callback);
    }

    template<typename T>
    void SplayTree<T>::in_order_traversal(SplayTree::callback_t callback) {
        in_order_traversal_helper(root_, callback);
    }

    template<typename T>
    void SplayTree<T>::post_order_traversal(SplayTree::callback_t callback) {
        post_order_traversal_helper(root_, callback);
    }

    template<typename T>
    void SplayTree<T>::level_order_traversal(SplayTree::callback_t callback) {
        breadth_first_traversal_helper(root_, callback);
    }


    //
    template<typename T>
    void SplayTree<T>::insert(const T& key) {

        //检索key的插入位置
        SplayTreeNode<T>* current{ root_ };
        SplayTreeNode<T>* parent{ nullptr };
        while (current) {
            parent = current;//记录要插入的父节点
            if (current->key_ < key) {
                current = current->right_;
            }
            else if (key < current->key_) {
                current = current->left_;
            }
        }

        //插入对应位置
        current = new SplayTreeNode(key);
        current->parent_ = parent;
        if (!parent) {
            root_ = current;
        }
        else if (parent->key_ < current->key_) {
            parent->right_ = current;
        }
        else if (current->key_ < parent->key_) {
            parent->left_ = current;
        }
        //平衡调整
        splay(current);
    }

    template<typename T>
    template<typename U>
    auto SplayTree<T>::search(const U& key) {
        auto res = search_helper(root_, key);
        return res ? std::optional<std::reference_wrapper<T>>{res->key_}
        : std::nullopt;
    }

    template<typename T>
    auto SplayTree<T>::minimum() {
        auto min = minimum_helper(root_);
        return min ? std::optional<std::reference_wrapper<T>>{min->key_}
        : std::nullopt;
    }

    template<typename T>
    auto SplayTree<T>::maximum() {
        auto max = maximum_helper(root_);
        return max ? std::optional<std::reference_wrapper<T>>{max->key_}
        : std::nullopt;
    }

    template<typename T>
    int SplayTree<T>::height() {
        return height_helper(root_);
    }

    template<typename T>
    int SplayTree<T>::size() {
        return size_helper(root_);
    }

    template<typename T>
    void SplayTree<T>::clear() {
        clear_helper(root_);
        root_ = nullptr;
    }

    //简单递归
    template<typename T>
    void SplayTree<T>::pre_order_traversal_helper(SplayTreeNode<T>* root, SplayTree::callback_t callback) {
        if (!root) return;
        callback(root->key_);
        pre_order_traversal_helper(root->left_, callback);
        pre_order_traversal_helper(root->right_, callback);
    }

    template<typename T>
    void SplayTree<T>::in_order_traversal_helper(SplayTreeNode<T>* root, SplayTree::callback_t callback) {
        if (!root) return;
        in_order_traversal_helper(root->left_, callback);
        callback(root->key_);
        in_order_traversal_helper(root->right_, callback);
    }

    template<typename T>
    void SplayTree<T>::post_order_traversal_helper(SplayTreeNode<T>* root, SplayTree::callback_t callback) {
        if (!root) return;
        post_order_traversal_helper(root->left_, callback);
        post_order_traversal_helper(root->right_, callback);
        callback(root->key_);
    }


    //经典宽搜
    template<typename T>
    void SplayTree<T>::breadth_first_traversal_helper(SplayTreeNode<T>* root, SplayTree::callback_t callback) {
        if (!root) return;
        std::queue<SplayTreeNode<T>*> queue;
        queue.push(root);
        while (!queue.empty()) {
            SplayTreeNode<T>* current{ queue.front() };
            callback(current->key_);
            queue.pop();
            if (current->left_) queue.push(current->left_);
            if (current->right_) queue.push(current->right_);
        }
    }





    //核心，调整平衡：每次都是把当爹的拉下马，自己上去
    template<typename T>
    void SplayTree<T>::splay(SplayTreeNode<T>* root) {
        //root指的是刚被访问过的节点
        while (root->parent_) {//当该节点还不是真正的根（父亲为空）
            if (!root->parent_->parent_) {//父亲就是根，
                if (root->parent_->left_ == root) {
                    //当前是左儿子，把父亲右旋下来
                    rotate_right(root->parent_);
                }
                else if (root->parent_->right_ == root) {
                    //当前是右儿子，把父亲左旋下来
                    rotate_left(root->parent_);
                }
            }
            //LL
            else if (root->parent_->left_ == root && 
                root->parent_->parent_->left_ == root->parent_) {
                rotate_right(root->parent_->parent_);
                rotate_right(root->parent_);
            }
            //RR
            else if (root->parent_->right_ == root && 
                root->parent_->parent_->right_ == root->parent_) {
                rotate_left(root->parent_->parent_);
                rotate_left(root->parent_);
            }
            //RL
            else if (root->parent_->left_ == root && 
                root->parent_->parent_->right_ == root->parent_) {
                rotate_right(root->parent_);
                rotate_left(root->parent_);
            }
            //LR
            else if (root->parent_->right_ == root && 
                root->parent_->parent_->left_ == root->parent_) {
                rotate_left(root->parent_);
                rotate_right(root->parent_);
            }
        }
    }

    template<typename T>
    void SplayTree<T>::rotate_left(SplayTreeNode<T>* rotation_root) {
        SplayTreeNode<T>* new_root{ rotation_root->right_ };
        SplayTreeNode<T>* orphan_subtree{ new_root->left_ };
        rotation_root->right_ = orphan_subtree;
        if (orphan_subtree) {
            orphan_subtree->parent_ = rotation_root;
        }
        new_root->left_ = rotation_root;
        if (!rotation_root->parent_) {
            root_ = new_root;
        }
        else if (rotation_root == rotation_root->parent_->left_) {
            rotation_root->parent_->left_ = new_root;
        }
        else {
            rotation_root->parent_->right_ = new_root;
        }
        new_root->parent_ = rotation_root->parent_;
        rotation_root->parent_ = new_root;
    }

    template<typename T>
    void SplayTree<T>::rotate_right(SplayTreeNode<T>* rotation_root) {
        SplayTreeNode<T>* new_root{ rotation_root->left_ };
        SplayTreeNode<T>* orphan_subtree{ new_root->right_ };
        rotation_root->left_ = orphan_subtree;
        if (orphan_subtree) {
            orphan_subtree->parent_ = rotation_root;
        }
        new_root->right_ = rotation_root;
        if (!rotation_root->parent_) {
            root_ = new_root;
        }
        else if (rotation_root == rotation_root->parent_->left_) {
            rotation_root->parent_->left_ = new_root;
        }
        else if (rotation_root == rotation_root->parent_->right_) {
            rotation_root->parent_->right_ = new_root;
        }
        new_root->parent_ = rotation_root->parent_;
        rotation_root->parent_ = new_root;
    }


    //简单递归
    template<typename T>
    template<typename U>
    SplayTreeNode<T>* SplayTree<T>::search_helper(SplayTreeNode<T>* root, const U& key) {
        //左 < root < 右
        while (root) {
            if (root->key_ < key) {
                root = root->right_;
            }
            else if (key < root->key_) {
                root = root->left_;
            }
            else {
                return root;
            }
        }
        return nullptr;
    }

    template<typename T>
    SplayTreeNode<T>* SplayTree<T>::minimum_helper(SplayTreeNode<T>* root) {
        //最小值一路向左
        if (!root) return nullptr;
        while (root->left_) root = root->left_;
        return root;
    }

    template<typename T>
    SplayTreeNode<T>* SplayTree<T>::maximum_helper(SplayTreeNode<T>* root) {
        //最大一路向右
        if (!root) return nullptr;
        while (root->right_) root = root->right_;
        return root;
    }

    template<typename T>
    int SplayTree<T>::height_helper(const SplayTreeNode<T>* root) {
        if (!root) return 0;
        return std::max(height_helper(root->left_), height_helper(root->right_)) + 1;
    }

    template<typename T>
    int SplayTree<T>::size_helper(const SplayTreeNode<T>* root) {
        if (!root) return 0;
        return size_helper(root->left_) + size_helper(root->right_) + 1;
    }

    template<typename T>
    void SplayTree<T>::clear_helper(SplayTreeNode<T>* root) {
        if (!root) return;
        if (root->left_) clear_helper(root->left_);
        if (root->right_) clear_helper(root->right_);
        delete root;
    }
}

简单测试

#include "SplayTree.h"
#include <iostream>
#include <string>
#include <utility>

using namespace ds;
using namespace std;



class Node {
public:
    Node() = default;
    Node(int key, std::string value) : key_(key), value_(std::move(value)) {};
    ~Node() = default;

    //操作符重载
    bool operator<(const Node& other) const { return key_ < other.key_; }
    friend bool operator<(const Node&, int);
    friend bool operator<(int, const Node&);
    friend std::ostream& operator<<(std::ostream&, const Node&);

    //伸展树只对key排序
    int key_ = 0;
    std::string value_;
};

bool operator<(const Node& lhs, const int rhs) { return lhs.key_ < rhs; }

bool operator<(const int lhs, const Node& rhs) { return lhs < rhs.key_; }

std::ostream& operator<<(std::ostream& os, const Node& node) {
    os << "(" << node.key_ << ", " << node.value_ << ")" << std::endl;
    return os;
}

int main() {
    ds::SplayTree<Node> tree;

    tree.insert(Node(2, "Thor"));
    tree.insert(Node(4, "Odin"));
    tree.insert(Node(90, "Loki"));
    tree.insert(Node(3, "Baldr"));
    tree.insert(Node(0, "Frigg"));
    tree.insert(Node(14, "Eir"));
    tree.insert(Node(45, "Heimdall"));

    //返回值optional中包含一个是否有值的判断，功能相当于std::pair<T,bool> ，但是更智能可读
    if (auto res = tree.search(2)) { std::cout << res->get() << std::endl; }

    //自定义匿名函数，作为参数
    tree.pre_order_traversal([](auto node) { std::cout << node << std::endl; });
    //tree.in_order_traversal([](auto node) { std::cout << node << std::endl; });
    //tree.post_order_traversal([](auto node) { std::cout << node << std::endl; });
    //tree.level_order_traversal([](auto node) { std::cout << node << std::endl; });

    //if (auto min = tree.minimum()) { std::cout << min->get() << std::endl; }
    //if (auto max = tree.maximum()) { std::cout << max->get() << std::endl; }

    //std::cout << tree.size() << std::endl;

    //std::cout << tree.height() << std::endl;

    tree.clear();

    return 0;
}