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

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

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

1. 关于数据的局部性

在任意数据结构的声明体内，不仅执行不同操作的概率往往极不均衡，而且操作之间具有极强的关联性。
数据局部性(data locality), 包含两层含义:

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

因此，对于二叉搜索树而言，只需将刚被访问的结点，及时地转移到根(root)附近，即可加速后续的操作。

2. 关于伸展树

伸展树(sply tree)是平衡二叉搜索树的一种形式。
它在每次查找之后对树进行重构，把被查找的条目搬移到离树根近一些的地方。
伸展树无需时刻都严格保持平衡，但却能够在任何足够长的真实操作序列中，保持分摊意义上的高效率。
伸展树不需要记录平衡因子、高度等用于平衡树的冗余信息。

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. 效果与效率

综上所述，每经过一次调整，结点v会上升两层。
无论v的初始深度depth(v)为偶数或奇数，经过depth(v)次旋转后，v最终总能成为树根。
伸展树每次操作的平摊时间复杂度是 $O(\log n)$ 。

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);
}

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

1. 关于数据的局部性

2. 关于伸展树

3. 重构方法

4. 效果与效率

5. 伸展树的实现

猜你喜欢

热点阅读