大师兄的数据结构学习笔记(十): 伸展树

2020-11-12  本文已影响0人  superkmi

大师兄的数据结构学习笔记(九): 图
大师兄的数据结构学习笔记(十一): B树

1. 关于数据的局部性

1) 刚被访问的元素,极有可能在不久后再次被访问。
2) 将被访问的下一个元素,极有可能就处于不久之前被访问过的某个元素附近。

2. 关于伸展树

3. 重构方法

1) zig-zig调整/zag-zag调整

假设:

  • v是p的左孩子,且p也是g的左孩子;
  • W和X分别是v的左、右子树,Y和Z分别是p和g的右子树。


  • 针对这种情况,首先以节点g为轴做顺时针旋转zig(g),其效果如图(b)所示。
  • 然后,再以p为轴做顺时针旋转zig(p),其效果如图(c)所示。
  • 如此连续的两次zig旋转,合称zig-zig调整
  • 如果是另一完全对称的情形,v是p的右孩子,且p也是g的右孩子,则可通过连续的
    两次逆时针旋转实现调整,合称zag-zag操作

2) zig-zag调整/zag-zig调整

假设:

  • v是p的左孩子,而p是g的右孩子;
  • W是g的左子树,X和Y分别是v的左右子树,Z是p的右子树。
  • 针对这种情况,首先以节点p为轴做顺时针旋转zig(p),其效果如(b)所示。
  • 然后,再以g为轴做逆时针旋转zag(g),其效果如图(c)所示。
  • 如此zig旋转再加zag旋转,合称zig-zag调整
  • 同样地,另一完全对称的情形–v是p的右孩子,而p是g的左孩子—则可通过zag旋转再加zig旋转实现调整,合称zag-zig操作

3) zig/zag调整

假设:

  • v最初的深度为奇数,则经过若干次双层调整至最后一次调整时,
  • 将v的左、右子树记作X和Y,节点p = r的另一子树记作Z。
  • v的父亲p即是树根r。
  • 此时,只需围绕p = r做顺时针旋转zig(p),即可如图(b)所示,使v最终攀升至树根,从而结束整个伸展调整的过程。
  • zag调整与之对称。

4. 效果与效率

5. 伸展树的实现

#ifndef SPLYTREE_H_
#define SPLYTREE_H_

template <typename T>
// 结点类
class Node
{
public:
    Node() :left(nullptr), right(nullptr) {} // 构造函数
    Node(T value, Node* l, Node* r) :key(value), left(l), right(r) {} // 带参构造函数
    T key;  //值
    Node* left; //左子树
    Node* right; //右子树
};

template <typename T>
// 伸展树类
class SplayTree
{
public:
    SplayTree();        //构造函数
    ~SplayTree();       //析构函数
    void preOrder();    //前序遍历
    void inOrder();     //中序遍历
    void postOrder();   //后序遍历
    Node<T>* search(T key); //查找值的结点
    void splay(T key);  //伸展
    void insert(T key); //插入结点
    void remove(T key); //删除结点
    void destroy();     // 销毁树
    void print();       //打印树
private:
    void preOrder(Node<T>* tree) const;
    void inOrder(Node<T>* tree) const;
    void postOrder(Node<T>* tree) const;
    Node<T>* search(Node<T>* x, T key) const;
    Node<T>* splay(Node<T>* tree, T key);
    Node<T>* insert(Node<T>*& tree, Node<T>* z);
    Node<T>* remove(Node<T>*& tree, T key);
    void destroy(Node<T>*& tree);
    void print(Node<T>* tree, T key, int direction);
private:
    Node<T>* _Root; // 根节点
};
#endif // !SPLYTREE_H_
#include <iostream>
#include <iomanip>
#include "Sply.h"
using namespace std;

template<class T>
// 构造函数
SplayTree<T>::SplayTree() :_Root(nullptr)
{

}

template<class T>
// 析构函数
SplayTree<T>::~SplayTree()
{
    destroy(_Root);
}

template<class T>
// 先序遍历
void SplayTree<T>::preOrder()
{
    preOrder(_Root);
}

template<class T>
void SplayTree<T>::preOrder(Node<T>* tree) const
{
    if (tree != nullptr)
    {
        cout << tree->key << " ";
        preOrder(tree->left);
        preOrder(tree->right);
    }
}

template<class T>
// 中序遍历
void SplayTree<T>::inOrder()
{
    inOrder(_Root);
}

template<class T>
void SplayTree<T>::inOrder(Node<T>* tree) const
{
    if (tree != nullptr)
    {
        inOrder(tree->left);
        cout << tree->key << " ";
        inOrder(tree->right);
    }
}

template<class T>
// 后序遍历
void SplayTree<T>::postOrder()
{
    postOrder(_Root);
}

template<class T>
void SplayTree<T>::postOrder(Node<T>* tree) const
{
    if (tree != nullptr)
    {
        postOrder(tree->left);
        postOrder(tree->right);
        cout << tree->key << " ";
    }
}

template<class T>
// 查找键值结点
Node<T>* SplayTree<T>::search(T key)
{
    return search(_Root, key);
}

template<class T>
Node<T>* SplayTree<T>::search(Node<T>* x, T key) const
{
    if (x == nullptr || x->key == key)
    {
        return x;
    }

    if (key < x->key)
    {
        return search(x->left, key);
    }
    else
    {
        return search(x->right, key);
    }
}

template<class T>
Node<T>* SplayTree<T>::splay(Node<T>* tree, T key)
{
    Node<T> N, * l, * r, * c;

    if (tree == nullptr)
    {
        return tree;
    }

    N.left = N.right = nullptr;
    l = r = &N;

    while(true)
    {
        if (key < tree->key) // zig
        {
            if (tree->left == nullptr)
            {
                break;
            }
            if (key < tree->left->key)  // zig 
            {
                c = tree->left;
                tree->left = c->right;
                c->right = tree;
                tree = c;
                if (tree->left == nullptr)
                    break;
            }
            r->left = tree;
            r = tree;
            tree = tree->left;
        }
        else if(key > tree->key)  //zag
        {
            if (tree->right == nullptr)
            {
                break;
            }
            if (key > tree->right->key)  //zag
            {
                c = tree->right;
                tree->right = c->left;
                c->left = tree;
                tree = c;
                if (tree->right == nullptr)
                {
                    break;
                }
            }
            l->right = tree;
            l = tree;
            tree = tree->right;
        }
        else 
        {
            break;
        }
    }
    l->right = tree->left;
    r->left = tree->right;
    tree->left = N.right;
    tree->right = N.left;
    return tree;
}

template<class T>
//伸展
void SplayTree<T>::splay(T key)
{
    _Root = splay(_Root, key);
}

template<class T>
Node<T>* SplayTree<T>::insert(Node<T>*& tree, Node<T>* z)
{
    Node<T>* y = nullptr;
    Node<T>* x = tree;

    while (x != nullptr) // 查找z的插入位置
    {
        y = x;
        if (z->key < x->key)
        {
            x = x->left;
        }
        else if (z->key > x->key)
        {
            x = x->right;
        }
        else
        {
            cout << "已包含结点:" << z->key << endl;
            delete z;
            return tree;
        }
    }

    if (y == nullptr)
        tree = z;
    else if (z->key < y->key)
    {
        y->left = z;
    }
    else
    {
        y->right = z;
    }
    return tree;
}

template<class T>
void SplayTree<T>::insert(T key)
{
    Node<T>* z = nullptr;
    if ((z = new Node<T>(key, nullptr, nullptr)) == nullptr)
        return;

    _Root = insert(_Root, z);
    _Root = splay(_Root, key);
}

template<class T>
Node<T>* SplayTree<T>::remove(Node<T>*& tree, T key)
{
    Node<T>* x;

    if (tree == nullptr) //如果树是空的
        return nullptr;

    if (search(tree, key) == nullptr) // 如果找不到
        return tree;

    tree = splay(tree, key); //跳到结点
    
    if (tree->left != nullptr)
    {
        x = splay(tree->left, key);
        x->right = tree->right;
    }
    else {
        x = tree->right;
    }

    delete tree;
    return x;
}

template<class T>
// 删除结点
void SplayTree<T>::remove(T key)
{
    _Root = remove(_Root, key);
}

template<class T>
// 销毁树
void SplayTree<T>::destroy()
{
    destroy(_Root);
}

template<class T>
void SplayTree<T>::destroy(Node<T>*& tree)
{
    if (tree == nullptr)
        return;
    if (tree->right != nullptr)
        destroy(tree->right);
    if (tree->left != nullptr)
        destroy(tree->left);

    delete tree;
}

template<class T>
//打印树
void SplayTree<T>::print()
{
    if (_Root != nullptr)
    {
        print(_Root, _Root->key, 0);
    }
}

template<class T>
void SplayTree<T>::print(Node<T>* tree, T key, int direction)
{
    if (tree == nullptr)
        return;

    if (direction == 0)
        cout << setw(2) << tree->key << "root" << endl;
    else
        cout<<setw(2)<<tree->key<<"is"<<setw(2)<<key<<"'s" << setw(12) << (direction == 1 ? "right child" : "left child") << endl;
    print(tree->left, tree->key, -1);
    print(tree->right, tree->key, 1);
}
上一篇下一篇

猜你喜欢

热点阅读