一、二叉查找树
简介
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
（2）若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的节点。
1.二叉查找树的遍历
在二叉查找树中，从小到大输出结点的值，只需要对二叉树进行中序遍历
void Print(int u) { if(!p[u].w) return; Print(p[u].lchild); printf("%d ",p[u].w); Print(p[u].rchild); //在二叉查找树中，从小到大输出结点的值，只需要对二叉树进行中序遍历 }
2.二叉查找树的查找
因为二叉查找树是有序的，所以要查找特定的值只需要二分查找即可，如果是非空结点，则查找成功，否则查找失败
int Find(int u) { if(!p[u].w) return 0; if(p[u].w==find_x) return u; if(p[u].w<find_x) return Find(p[u].rchild); if(p[u].w>find_x) return Find(p[u].lchild); //因为二叉查找树是有序的，所以要查找特定的值只需要二分查找即可，如果是非空结点，则查找成功，否则查找失败 }
3.二叉查找树查找最值
找到以u为树根的权值最小的点,此点一定是u的递归操作下的左子树中的叶子结点
int Find_Min(int u) { if(!p[u].w) return 0; while(p[p[u].lchild].w) u=p[u].lchild; return u;//找到以u为树根的权值最小的点,此点一定是u的递归操作下的左子树中的叶子结点 }
4.二叉查找树中插入结点
建立在查找的基础上，二分查找，注意的是可能有重复的点，这时候有两个解决方法
①插入到左子树中
②将结点打计数标记
假如当前结点为空，建立新的结点，结点的值就是当前插入结点的值，生成左右空子树
void Insert(int u) { if(!p[u].w) {p[u].w=insert_x,p[u].cnt++;} if(p[u].w<find_x) return Insert(p[u].rchild); if(p[u].w>find_x) return Insert(p[u].lchild); /*假如当前结点为空，建立新的结点，结点的值就是当前插入结点的值，生成左右空子树 有重复的结点的话，打计数标记解决 */ }
5.二叉查找树中删除结点
分三种情况讨论
①叶子结点
②链结点
③有两个非空子节点
前面两个同样对待，用叶子结点代替本身，就等于用空节点代替，等同于删除
对于第三种情况，删除结点u，要用右子树中最小的值代替
int Delete_Min(int u) { if(!p[u].lchild) return u; else return Delete_Min(p[u].lchild); /*如果左子树为空，则直接用自己代替 否则继续遍历左子树 */ } void Delete(int u) { if(p[u].w==delete_p) { if(p[u].cnt>1) {p[u].cnt--;return;} if(p[u].rchild&&p[u].lchild) p[u]=p[Delete_Min(p[u].rchild)]; else p[u]=p[p[u].lchild+p[u].rchild]; return; /*找到值相同的节点，如果节点的cnt>1直接处理返回 如果发现是链结点或者叶子结点，直接继承两个儿子的序列和的那一个节点 假使是链节点的话，那么必定有一个结点为空，如果是叶子结点，都为空，就等同与删除了此叶子结点 */ } if(delete_p<p[u].lchild) Delete(p[u].lchild); else Delete(p[u].rchild); }
二、Treap
1.Treap 旋转(Zig/Zag)
左旋
右旋
