int Search_Seq(int ST[],int key)
{
for(int i=ST.length-1;i>=0;--i)
{
if(ST[i] == key)
return i;
}
return -1;
}
int Search_Bin(int ST[],int key)
{
int low = 0,high = ST.length-1;
while(low<=high)
{
int mid = (low+high)/2;
if(ST[mid]<key)
high = mid - 1;
else if(ST[mid]>key)
low = mid +1;
else
return mid;
}
return -1;
}
//注意没有回溯的过程
bool SearchBST(BiTree T,KeyType key,BiTree &f,Bitree& p)
{
//如果没有找到则返回路径的最后一个叶节点
if(!T){
p = f;
return false;
}
//如果找到了则返回该节点
if(T->data == key){
p = T;
return true;
}
else if(T->data > key)
return (SearchBST(T->lchild,key,T,p));
else
return (SearchBST(T->rchild,key,T,p));
}
bool InsertBST(BiTree& T,ElemType e)
{
Bitree p;
//如果已有相同节点返回false
if(searchBST(T,e,key,NULL,p))
return false;
Bitree s= (BiTree)malloc(sizeof(BiNode));
s->data = e;
s->lchild = s->rchild = NULL;
if(!p) T = s; //如果树不存在则将s作为根结点
else if(s->data < p->data)
p->lchild = s;
else
p->rchild = s;
return true;
}
bool DeleteBST(BiTree& T,KeyType key)
{
BiTree f = nullptr,p = nullptr;
if(!SearchBST(T,key,f,p))
return false;
//对应第一种情况，p为叶子结点
if(f == p)
free(p);
//对应第三种情况，p既有左子树又有右子树
if(p->lchild!=nullptr && p->rchild!=nullptr)
{
//将左子树插到父节点上面
if(p == f->lchild){
f->lchild = p->lchild;
}
else{
f->rchild = p->lchild;
}
Bitree tmp = p->lchild;
while(tmp->rchild!=nullptr)
tmp = tmp->rchild;
tmp->rchild = p->rchild;
free(p);
}
//对应第二种情况，只有左子树或者只有右子树
else
{
if(p == f->lchild){
p->lchild == nullptr ? f->lchild = p->rchild:f->lchild = p->lchild;
free(p);
}
else{
p->lchild == nullptr ? f->rchild = p->rchild:f->lchild = p->lchild;
free(p);
}
}
}
typedef struct BSTNode
{
ElemType data;
int bf;
struct BSTNode* lchild,*rchild;
}BSTNode,*BSTree;
void R_Rotate(BSTree& p)
{
BSTNode* tmp = p->lchild;
p->lchild = tmp->rchild;
tmp->rchild = p;
p = tmp;
}
void L_Rotate(BSTree& p)
{
BSTNode* tmp = p->rchild;
p->rchild = tmp->lchild;
tmp->lchild = p;
p = tmp;
}
typedef struct node {
int val;
struct node* left, * right;
}node,*tree;
void rotateLeft(tree& root) {
node* t = root->right;
root->right = t->left;
t->left = root;
root = t;
}
void rotateRight(tree& root) {
node* t = root->left;
root->left = t->right;
t->right = root;
root = t;
}
void rotateLeftRight(tree& root) {
rotateLeft(root->left);
rotateRight(root);
}
void rotateRightLeft(tree& root) {
rotateRight(root->right);
rotateLeft(root);
}
int getHeight(tree& root) {
if (root == nullptr) return 0;
return max(getHeight(root->left), getHeight(root->right)) + 1;
}
void insert(tree& root, int val) {
if (root == nullptr) {
root = new node();
root->val = val;
root->left = root->right = nullptr;
return;
}
else if (val < root->val) {
insert(root->left, val);
if (getHeight(root->left) - getHeight(root->right) == 2)
val < root->left->val ? rotateRight(root) : rotateLeftRight(root);
}
else {
insert(root->right, val);
if (getHeight(root->left) - getHeight(root->right) == -2)
val > root->right->val ? rotateLeft(root) : rotateRightLeft(root);
}
}
在动态插入中保证树的完美平衡的代价太高了，所以有了为了依旧保持树高为lgN，有了2-3查找树和下面的红黑树
我们将一棵标准的二叉查找树中的结点称为2-结点（含有一个键和两条链接），而现在我们引入3- 结点，它含有两个键和三条链接
插入：
（1）向2-结点中插入新键
（2）向一棵只含有一个3-结点的树中插入新键
在考虑一般情况之前，先假设我们需要向一棵只含有一 个 3-结点的树中插人一个新键。这棵树中有两个键，所以在它唯一的结点中已经没有可插人新键的空间了。为了将新键插人，我们先临时将新键存入该结点中，使之成为一个4-结点。它很自然地扩展了以前的结点并含有3个键和4条链接。创建一个4- 结点很方便，因为很容易将它转换为一棵由3个2-结点组成的2-3树，其中一个结点（根 )含有中键，一个结点含有3个键中的最小者（和根结点的左链接相连) ，一个结点含有3个键中的最大者（和根结点的右链接相连）。这棵树既是一棵含有3个结点的二叉查找树，同时也是一棵完美平衡的2-3 树
（3）向一个父节点为2- 结点的3- 结点插入新键
，假设未命中的查找结束于一个3-结点，而它的父结点是一个2-结点。在这 种情况下我们需要在维持树的完美平衡的前提下为新键腾出空间。我们先像刚才一样构造一个临时的4-结点并将其分解，但此时我们不会为中键创建一个新结点，而是将其移动至原来的父结点中。你可以将这次转换看成将指向原3- 结点的一条链接替换为新父结点中的原中键左右两边的两条链 接，并分别指向两个新的2-结点。根据我们的假设，父结点中是有空间的：父结点是一个2-结点（一 个键两条链接），插人之后变为了一个3-结点（两个键3 条链接）。另外，这次转换也并不影响（完 美平衡的）2-3树的主要性质。树仍然是有序的，因为中键被移动到父结点中去了；树仍然是完美平衡的，插入后所有的空链接到根结点的距离仍然相同
（4）向一个父节点为3- 结点的3- 结点中插入新键
现在假设未命中的查找结束于一个父结点为3- 结点的结点。我们再次和刚才一样构造一个 临时的4-结点并分解它，然后将它的中键插入它的父结点中。但父结点也是一个3-结点，因此 我们再用这个中键构造一个新的临时4-结点，然后在这个结点上进行相同的变换，即分解这个 父结点并将它的中键插入到它的父结点中去。推广到一般情况，我们就这样一直向上不断分解临 时的4-结点并将中键插入更高层的父结点，直至遇到一个2- 结点并将它替换为一个不需要继续 分解的3-结点，或者是到达3-结点的根
如果从插入结点到根结点的路径上全都是3-结点，我们的根结点最终变成一个临时的4-结点。
此时我们可以按照向一棵只有一个3-结点的树中插入新键的方法处理这个问题。我们将临时的4- 结点分解为3个 2-结点，使得树高加1 , 如图3.3.7所示。请注意，这次最后的变换仍然保持了树 的完美平衡性，因为它变换的是根结点
红黑二叉查找树背后的基本思想是用标准的二叉查找树（完全有2-结点构成）和一些额外的信息（替换3-结点）来表示2-3树。
我们将树中的链接分为两种类型：红链接将两个2- 结点连 接起来构成一个3-结点，黑链接则是2-3树中的普通链接。确 切地说，我们将3-结点表示为由一条左斜的红色链接（两个2- 结点其中之一是另一个的左子结点）相连的两个2-结点，如图 3.3.12所示。这种表示法的一个优点是，我们无需修改就可以直 接使用标准二叉查找树的g e t()方法。对于任意的2-3树，只要对结点进行转换，我们都可以立即派生出一棵对应的二叉查找树
红黑树的另一种定义是含有红黑链接并满足下列条件的二叉查找树：
- 红链接均为左链接
- 没有任何一个结点同时和两条红链接相连
- 该数是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同
如果我们将一棵红黑树的红链接画平，那么所有的空链接到根结点的距离都将是相同的。如下图所示：
如果我们将会由红链接相连的结点合并，得到的就是一棵2-3树。无论我们选择用何种方式去定义它们，红黑树都既是二叉查找树，也是2-3树。因此，如果我们能够在保持一一对应关系的基础上实现2-3的插入算法，那么我们就能够将两个算法的优点结合起来：二叉查找树中简洁高效的查找方法和2-3树中高效的平衡插入算法
为了方便起见，因为每个结点都只会有一条指向自己的链接，我们将链接的颜色保存在表示结点的Node数据类型的布尔变量color中。如果指向它的链接是红色的，那么该变量为true，黑色则为false。
#define RED true
#define BLACK false
typedef int Key;
typedef struct
{
Key key; //键
Node* left, *right;
bool color;
}Node,*RBTree;
在我们实现的某些操作中可能会出现红色右链接或者两条连续的红链接，但在操作完成前这些情况都会被小心地旋转并修复。旋转操作会改变红链接的指向
假设我们有一条红色的右链接需要被转化为左链接。这个操作叫做左旋转
左旋前：
左旋后：
void RotateLeft(RBTree& h)
{
Node* tmp = h->right;
h->right = tmp->left;
tmp->color = h->color;
h->color = RED;
tmp->left = h;
h = tmp;
}
实现将一个红色左链接转换为一个红色右链接的一个右旋 转的代码完全相同，只需要将left换成right即可
void RotateRight(RBTree& h)
{
Node* tmp = h->left;
h->left = tmp->right;
tmp->color = h->color;
h->color = RED;
tmp->right = h;
h = tmp;
}
无论左旋转还是右旋转，旋转操作都会返回一条链接。我们总是会用rotateRight( ) 或 rotateLeft()的返回值重置父结点（或是根结点）中相应的链接。返回的链接可能是左链接也可能是右链接，但是我们总会将它赋予父结点中的链接。这个链接可能是红色也可能是黑色—— rotateLeft() 和 rotateRight() 都通过将x.color设为h.color保留它原来的颜色。这可能会产生两条连续的红链接，但我们的算法会继续用旋转操作修正这种情况。
插入：
（1）向根结点插入新键
一棵只含有一个键的红黑树只含有一个2-结点。插入另一个键之后，我们马上就需要将它们旋转。如果新键小于老键，我们只需要新增一个红色的结点即可，新的红黑树和单个3- 结点完全等价。如果新键大于老键，那么新增的红色结点将会产生一条红色的右链接。我们需要使用root = RotateLeft(root);来将其旋转为红色左链接并修正根结点的链接，插入操作才算完成
（2）向树底部的2- 结点插入新键
用和二叉查找树相同的方式向一棵红黑树中插入一个新键会在树的底部新增一个结点（为了保 证有序性），但总是用红链接将新结点和它的父结点相连。如果它的父结点是一个2-结点，那么 刚才讨论的两种处理方法仍然适用。如果指向新结点的是父结点的左链接，那么父结点就直接成为 了一个3-结点；如果指佝新结点的是父结点的右链接，这就是一个错误的3-结点，但一次左旋转 就能够修正它
（3）向一棵双键树（即一个3- 结点）中插入新键
①新键大于原树中的两个键
②新键小于原树中的两个键
③新键介于两者之间
在上述步骤的颜色变换，不仅要将子结点变黑，还要将父结点变红，于是我们单独封装一个函数：
void flipColors(RBTree& h)
{
h->color = RED;
h->left->color = BLACK;
h->right->color = BLACK;
}
注意：在上述情况中，颜色转换会让根结点变红，严格地说，红色的根结点说明根结点是一个3- 结点的一部分，但实际情况并不是这样。因此我们在每次插入后都会将根结点设为黒色。（注意，每当根结点由红变红黑时树的黑链接高度就会加1）
红黑树的递归思想
2-3树中的插人算法需要我们分解3-结点，
将中间键插入父结点，如此这般直到遇到一个2- 结点或是根结点。我们所考虑过的所有情况都正是为了达成这个目标：每次必要的旋转之后我们都会进行颜色转换，这使得中结点变红。在父结点看来，处理这样一个红色结点的方式和处理一个新插入的红色结点完全相同，即继续把红链接转移到中结点上去。
实现代码：
bool Insert(RBTree h, Key key)
{
//如果树为空
if (h == nullptr) {
h = (Node*)malloc(sizeof(h));
h->color = RED;
h->key = key;
h->left = h->right = nullptr;
return;
}
if (key < h->key) Insert(h->left, key);
else if (key > h->key) Insert(h->right, key);
else return false;
if (h->left->color == RED && h->right->color == RED) flipColors(h);
if (h->left->left->color == RED && h->left->color == RED) RotateRight(h);
if (h->right->color == RED && h->left->color == BLACK) RotateLeft(h);
}
void InsertRBTree(RBTree root,Key key)
{
Insert(root, key);
root->color = BLACK;
}
删除：
首先我们要回到2-3树。和插入操作一样，我们也可以定义一系列局部变换来删除一个结点的同时保持树的完美平衡性。这个过程比插入一个结点更加复杂，因为我们不仅要在（为了删除一个结点而）构造临时4-结点时沿着查找路径向下进行变换，还要再分解遗留的4-结点时沿着查找路径向上进行变换（同插入操作）
（1）删除最小值
在第二轮热身中我们要学习2-3树中删除最小键的操作。我们注意到从树底部的3- 结点中删除 键是很简单的，但 2-结点则不然。从 2-结点中删除一个键会留下一个空结点，一般我们会将它替 换为一个空链接，但这样会破坏树的完美平衡性。所以我们需要这样做：为了保证我们不会删除一 个 2-结点，我们沿着左链接向下进行变换，确保当前结点不是2-结 点 （可能是3-结点，也可能是 临时的4-结点）。首先，根结点可能有两种情况。如果根是2-结点且它的两个子结点都是2-结点，
我们可以直接将这三个结点变成一个4-结点；否则我们需要保证根结点的左子结点不是2-结点，如有必要可以从它右侧的兄弟结点“借” 一个键来。以上情况如图3.3.26所示。在沿着左链接向下 的过程中，保证以下情况之一成立:
- 如果当前结点的左子结点不是2-结点，完成
- 如果当前结点的左子结点是2-结点而它的亲兄弟结点不是2-结点，将左子结点的兄弟结点 中的一个键移动到左子结点中
- 如果当前结点的左子结点和它的亲兄弟结点都 是 2-结点，将左子结点、父结点中的最小键 和左子结点最近的兄弟结点合并为一个4- 结 点，使父结点由3-结点变为2-结点或者由4- 结点变为3-结点。
在遍历的过程中执行这个过程，最后能够得到一 个含有最小键的3-结点或者4-结点，然后我们就可 以直接从中将其删除，将 3-结点变为2-结点，或者 将 4-结点变为3-结点。然后我们再回头向上分解所有临时的4-结点。
删除最小值代码：
void moveRedLeft(RBTree& root)
{
flipColors(root);
if (isRed(root->right->left)) {
RotateRight(root->right);
RotateLeft(root);
flipColors(root);
}
}
void balance(RBTree& h)
{
if (isRed(h->right) && !isRed(h->left)) RotateLeft(h);
if (isRed(h->left->left) && isRed(h->left)) RotateRight(h);
if (isRed(h->left) && isRed(h->right)) flipColors(h);
}
void deleteMin(RBTree& h)
{
if (h->left == nullptr) {
delete h;
return;
}
if (!isRed(h->left) && !isRed(h->left->left))
moveRedLeft(h);
deleteMin(h->left);
balance(h);
}
void DeleteMin(RBTree& root)
{
if (!isRed(root->left) && !isRed(root->right))
root->color = RED;
deleteMin(root);
if (root != nullptr)
root->color = BLACK;
}
（2）删除最大值：
基本与删除最小值对称
void moveRedRight(RBTree& root)
{
flipColors(root);
if (isRed(root->left->left)) {
//此时只需要做一次旋转
RotateRight(root->left);
flipColors(root);
}
}
void deleteMax(RBTree& h)
{
if(isRed(h->left))
RotateRight(h);
if (h->right == nullptr) {
delete h;
return;
}
if (!isRed(h->rightt) && !isRed(h->right->left))
moveRedLeft(h);
deleteMin(h->right);
balance(h);
}
void DeleteMax(RBTree& root)
{
if (!isRed(root->right) && !isRed(root->left))
root->color = RED;
deleteMax(root);
if (root != nullptr)
root->color = BLACK;
}
请注意：在deleteMax中不是直接判断是不是已经到了最大的结点，而是加了一个判断语句，因为如果最大结点是根结点的情况，如果直接删除会丢失掉左子树，所以要进行一次右旋转。
那么为什么不会出现最小结点是根结点的情况呢，这就跟红黑树的性质有关了：
红黑树只会出现右图的情况，而不会出现左图的情况
总删除代码：
void Delete(RBTree& root,Key key)
{
if (!isRed(root->left) && !isRed(root->right))
root->color = RED;
delete(root,key);
if (root != nullptr)
root->color = BLACK;
}
void delete(RBTree& h,Key key)
{
if(key<h->key){
if (!isRed(h->left) && !isRed(h->left->left))
moveRedLeft(h);
delete(h->left,key);
}
else{
if(isRed(h->left))
RotateRight(h);
if(key == h.key && h->right ==nullptr)
delete h;
if (!isRed(h->right) && !isRed(h->right->left))
moveRedLeft(h);
if(key == h.key){
Node* x = min(root->right);
h->key = x->key;
deleteMin(h->right);
}
delete(h->right,key);
}
balance(h);
}
#define m 3
typedef struct BTNode
{
int keynum; //结点关键字个数
struct BTNode* parent;
KeyType key[m+1]; //关键字向量，0留空
struct BTNode *ptr[m+1]; //子树指针向量
}BTNode,*BTree;
typdef struct
{
BTNode* pt; //指向周到的结点
int i; //在结点中的关键字序号
int tag; // 1:查找成功 0:查找失败
}Result;
Result SearchBTree(BTree T,KeyType K)
{
BTNode* q = nullptr,*p = T;
int i = 0;
while(p)
{
i = Search(p,K);
if(i > 0 && p->key[i] == K)
return Result(p,i.1);
else{
q = p;
p = p->ptr[i];
}
}
return Result(q,i,0); //查找不成功，返回k的插入位置信息
}
int Search(BTree T,KeyType key)
{
int low = 1,high = T.keynum;
bool little = false;
while(low<=high)
{
int mid = (low+high)/2;
if(T->key[mid]<key)
high = mid - 1;
else if(T->key[mid]>key)
low = mid +1;
else
return mid;
}
return high;
}
bool InsertBTree(BTree& T,KeyType K,BTree q,int i)
{
while(q)
{
Insert(q,i,x);
if(q->keynum<m)
break;
int s = ceil(m/2);
split(q,s);
x = q->keys[s];
q = q->parent;
if(q)
i = Search(q,x);
}
if(!q)
NewRoot(T,q,x);
return true;
}
#define SUCCEESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
int hashsize[n] = {}; //哈希表容量递增表，一个合适的素数序列
typedef struct
{
ElemType *elem;
int count; //当前数据元素个数
int sizeindex; //hashsize[sizeindex]为当前容量
}HashTable;
bool SearchHash(HashTable H,KeyType K,int& p,int& c)
{
p = Hash(k); //求得哈希地址
while(H.elem[p].key!=NULL && H.elem[p].key != K)
collision(p,++c);
if(K == H.elem[p].key)
return SUCCESS;
else
return UNSUCCESS;
}
bool InsertHash(HashTable& H,ElemType e)
{
c = 0;
int p;
if(SearchHash(H,e.key,p,c))
return DUPLICATE;
else if(c<hashsize[H.sizeindex]/2)
{
H.elem[p] = e;
++H.count;
return truel;
}
else
{
//重建Hash表
RecreateHashTable(H);
return UNSUCCESS;
}
}
因篇幅问题不能全部显示，请点此查看更多更全内容
Copyright © 2019- 99spj.com 版权所有 湘ICP备2022005869号-5
违法及侵权请联系：TEL:199 18 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务