admin 管理员组文章数量: 1086019
伸展树及相关操作
伸展树
简要提点
- 伸展树（Splay Tree）是一种二叉排序树，能在O(log n)内完成插入、查找和删除操作。
- 伸展树的基本操作都和伸展有关：当带有关键字X的节点被插入时，需要对树进行一系列的伸展旋转使得关键字X的节点成为新的根节点。当查找一个关键字X时，也同样对树进行伸展旋转使得带有关键字X的节点成为根节点。这样下次再查找X时，只需O(1)的时间。
- 伸展树的数据结构使得访问频繁的关键字排在靠近根的位置，减少了频繁关键字的查找时间。
伸展树的旋转
- 三种旋转情况：单旋转、一字形旋转和之字形旋转，每种旋转都分左右两个方向。
- 为了简化旋转操作，假设当前伸展树根节点X，左边有个空节点L节点（旋转过程作为子树的根，自顶向下迭代过程中子树中存放小于X的节点），同样右边有个空节点R节点（旋转过程作为子树的根，自顶向下迭代过程中子树中存放大于X的节点）当然也可以不借助L和R直接在树中自顶向下依次旋转调整。
单旋转
- 如下图假设（要查找的）目标节点为 Y Y 节点，则需要进行一次单旋转（左），将
Y " role="presentation" style="position: relative;">调整为中间树的新根。
一字形旋转
- 类似于AVL树的单旋转如下图假设（要查找的）目标节点为 Z Z 节点，则需要进行一次一字形旋转（左），将
Z " role="presentation" style="position: relative;">调整为中间树的新根。
SplayTree SingleRotateWithLeft(SplayTree Sp) // 一字形旋转（左）类似AVL单左旋
{SplayNode* X = Sp; SplayNode* Y = Sp->left; // 用X和Y标记树的根节点及左孩子X->left = Y->right; // X的左孩子赋值为Y的右孩子Y->right = X;return Y; // 返回Y
}之字形旋转
- 类似于AVL树的双旋转，如下图假设（要查找的）目标节点为 Z Z 节点，则需要进行一次之字形调整，将
Z " role="presentation" style="position: relative;">调整为中间树的新根。
之字形旋转简化
- 将目标节点的父节点作为新根，可以把之字形旋转简化为单旋转。优点：简化程序。缺点：展开过程需要进行更多迭代。
- 如下图假设（要查找的）目标节点为 Z Z <script type="math/tex" id="MathJax-Element-1096">Z</script>节点，简化之字形旋转为单旋转，将其父节点Y调整为中间树的新根。
旋转后的链接
- 进行旋转后，要对L、R及中间树进行链接形成一颗新树。如下图
伸展树的展开操作
- 伸展树的关键就在于其伸展操作
SplayTree Splay(SplayTree Sp, ElementType key) // 自顶向下的展开过程
{SplayTree L = Initialize(); // 借助L和R实现展开过程SplayTree R = Initialize();SplayNode* LeftTreeMax = L; // 定义LeftTreeMax指针指向左子树的最大关键字所在的节点SplayNode* RightTreeMin = R; // 定义RightTreeMin指针指向右子树的最小关键字所在的节点while (Sp && key != Sp->value) // 自顶向下依次迭代伸展{if (key < Sp->value) {if (Sp->left && key < Sp->left->value) // 一字形旋转（左）的条件 Sp = SingleRotateWithLeft(Sp);if (!Sp->left)break;// 连接到R中，当不满足一字形旋转条件时，下面两句是直接执行单旋转RightTreeMin->left = Sp; RightTreeMin = Sp;Sp = Sp->left; // 迭代往左}else{if (Sp->right && key > Sp->right->value) // 一字形旋转（右）的条件Sp = SingleRotateWithRight(Sp);// 连接到L中，当不满足一字形旋转时，下面两句是直接执行单旋转if (!Sp->right)break;LeftTreeMax->right= Sp;LeftTreeMax = Sp;Sp = Sp->right; // 迭代往右}}// 重构树LeftTreeMax->right = Sp->left;RightTreeMin->left = Sp->right;Sp->left = L->right;Sp->right = R->left;return Sp;
}
附伸展树实现及其相关操作C/C++
#include<iostream>
using namespace std;#define ElementType inttypedef struct TreeNode { // 定义树节点结构ElementType value; // 关键字值TreeNode* left; // 左孩子TreeNode* right; // 右孩子
}SplayNode, *SplayTree; static SplayNode* NullNode = nullptr; // 定义一个空节点静态局部变量，初始化为空指针SplayTree Initialize()
{SplayTree Sp = new SplayNode;Sp->left = nullptr;Sp->right = nullptr;return Sp;
}SplayTree SingleRotateWithLeft(SplayTree Sp) // 一字形旋转（左）类似AVL单左旋
{SplayNode* X = Sp; SplayNode* Y = Sp->left; // 用X和Y标记树的根节点及左孩子X->left = Y->right; // X的左孩子赋值为Y的右孩子Y->right = X;return Y; // 返回Y
}SplayTree SingleRotateWithRight(SplayTree Sp) // 一字形旋转（右）类似AVL单右旋
{SplayNode* X = Sp;SplayNode* Y = Sp->right; // 用X和Y标记树的根节点及右孩子X->right = Y->left; // X的右孩子赋值为Y的左孩子Y->left = X;return Y; // 返回Y
}SplayTree Splay(SplayTree Sp, ElementType key) // 自顶向下的展开过程
{SplayTree L = Initialize(); // 借助L和R实现展开过程SplayTree R = Initialize();SplayNode* LeftTreeMax = L; // 定义LeftTreeMax指针指向左子树的最大关键字所在的节点SplayNode* RightTreeMin = R; // 定义RightTreeMin指针指向右子树的最小关键字所在的节点while (Sp && key != Sp->value) // 自顶向下依次迭代伸展{if (key < Sp->value) {if (Sp->left && key < Sp->left->value) // 一字形旋转（左）的条件 Sp = SingleRotateWithLeft(Sp);if (!Sp->left)break;// 连接到R中，当不满足一字形旋转条件时，下面两句是直接执行单旋转RightTreeMin->left = Sp; RightTreeMin = Sp;Sp = Sp->left; // 迭代往左}else{if (Sp->right && key > Sp->right->value) // 一字形旋转（右）的条件Sp = SingleRotateWithRight(Sp);// 连接到L中，当不满足一字形旋转时，下面两句是直接执行单旋转if (!Sp->right)break;LeftTreeMax->right= Sp;LeftTreeMax = Sp;Sp = Sp->right; // 迭代往右}}// 重构树LeftTreeMax->right = Sp->left;RightTreeMin->left = Sp->right;Sp->left = L->right;Sp->right = R->left;return Sp;
}SplayTree Insert(SplayTree Sp, ElementType key) // 向伸展树中插入关键字key
{static SplayNode* NewNode = nullptr;if (!NewNode){NewNode = new SplayNode;}NewNode->value = key;if (!Sp){Sp = Initialize();Sp->value = key;}else{Sp = Splay(Sp, key); // 展开if (key < Sp->value){NewNode->left = Sp->left;NewNode->right = Sp;Sp->left = nullptr;Sp = NewNode;}else if (key > Sp->value){NewNode->right = Sp->right;NewNode->left = Sp;Sp->right = nullptr;Sp = NewNode;}elsereturn Sp; // 关键字已经在树中}NewNode = nullptr;return Sp;
}void Preorder(const SplayTree &Sp) // 先序遍历树
{if (Sp != nullptr){cout << Sp->value << " ";Preorder(Sp->left);Preorder(Sp->right);}
}void Find(SplayTree &Sp, ElementType key) // 在伸展树中查找关键字key
{if (Sp == nullptr){cout << "Empty Tree\n";return;}else{Sp = Splay(Sp, key); // 展开if (key == Sp->value){cout << Sp->value<<" Has been Found!" << endl;}else{cout << "The number is not in the tree.\n";}}
}SplayTree Delete(SplayTree Sp, ElementType key)
{SplayTree NewTree = Initialize();if (Sp != nullptr){Sp = Splay(Sp, key); // 按关键字key展开树，使带key节点成为新的根节点if (key == Sp->value){if (Sp->left == nullptr) // 如果调整后的伸展树左孩子为空，NewTree = Sp->right; // 则newTree为其右孩子else{//NewTree = Sp->left; // 新树的根节点指向旧树的左孩子NewTree = Splay(Sp->left, key); // 重新按照key调整新树NewTree->right = Sp->right; // 新树的右孩子指向旧树的右孩子}delete Sp;}}return NewTree;
}int main()
{int A[] = { 16,13,18,15,24,20,30,5,25,12,2 };SplayTree SpTree = nullptr;for (int i = 0;i < sizeof(A) / sizeof(int);i++){SpTree = Insert(SpTree, A[i]);}cout << "The preorder print of the Tree is: \n";Preorder(SpTree);int number;cout << "\nInput a number to find:\n";cin >> number;Find(SpTree, number);cout << "The preorder print of the Tree is: \n";Preorder(SpTree);cout << "\nDelete the number " << number << " from the tree.\n";SpTree = Delete(SpTree, number);cout << "The preorder print of the Tree is: \n";Preorder(SpTree);cout << endl;system("pause");return 0;
}运行结果
The preorder print of the Tree is:
2 5 12 13 25 24 18 15 16 20 30
Input a number to find:
16
16 Has been Found!
The preorder print of the Tree is:
16 5 2 13 12 15 24 18 20 25 30
Delete the number 16 from the tree.
The preorder print of the Tree is:
15 13 5 2 12 24 18 20 25 30
请按任意键继续. . .参考资料
Mark Allen Weiss: 数据结构与算法分析
本文标签： 伸展树及相关操作
版权声明：本文标题：伸展树及相关操作 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1688023799a170033.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论