大师兄的数据结构学习笔记(九）: 图
大师兄的数据结构学习笔记(十一）: 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最终总能成为树根。
- 伸展树每次操作的平摊时间复杂度是
。
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);
}
