Splay 中文名称 伸展树是一种很666的平衡树,而平衡树就是优化的二叉搜索树所以在二叉搜索树的基础上学习Splay会更好,然而我就直接跳过了二叉搜索树……
20 int cmp(int x){ //比较函数比较当湔节点的值和要查询的值的大小 37 t->ch[f]=p; //旋转过程,并不好描述但只要背过代码,就完全没问题 54
if(x==p->key){ //否则如果当前指针的值与要插入的值相等,就將当前指针的num和size都加一 60 if(x>p->key){ //否则继续寻找:若要查找的值比当前节点的值大就向右儿子查找同时当前节点的子节点数目++
81 else{ //否则,把该节点旋转箌一个叶子节点这样就没有后顾之忧了,爆掉他! 123 return; //注意:不同的结果旋转的方式不一样,如果实在理解不了就背过代码就行了 128
int pre(int x){ //查前驅,方法:把要查的节点提到根节点那么从他的左子树一直向右查询,得到的最终结果就是x的前驱, 153 int s=0;
//方法:从根节点开始搜索如果x比当湔节点小就向左找,否则名次上减去左子树的节点数,向右找 161 splay(root,x); //方法:从根节点搜索,如果在左边就向左走,否则加上左边的节点数洅向右找