数据结构与算法：
0.散列的实验：在线性开型的散列表实现中。我刚开始错误的认为删除一个元素时只需要将同一个模n同余类下的元素进行相应的移动即可，但是忽略的一个问题——那就是如果其他桶基点的模n同余类没有在本位，而当前删除的模n同余类却进行了位移，将会造成一个或多个空位。而这些空位将会直接导致对应的模n同余类数据损失。最后改正了这一点成功AC（代码可展开）：
1 void hashClass::erase(int target){ 2 3 int k=target; 4 int b=search(target); //e的起始桶 5 int count=0; 6 if(table[b]==-1) //如果起始同为空 7 { 8 cout<<"Not Found"<<endl; 9 10 } 11 else if(table[b]==k) 12 13 { 14 table[b]=-1; 15 int i=b; 16 int z=b; 17 int x; 18 do{ 19 i=(i+1)%divisor; //起始桶下一个元素 20 if(table[i]==-1) //如果为空 21 { 22 break; 23 } 24 x=table[i]%divisor; //起始桶下一个元素 的起始桶 25 if(i!=x&&x<=z&&i>z){ //起始桶下一个元素不等于x， 26 table[z]=table[i]; 27 table[i]=-1; 28 // cout<<"把索引 "<<i<<" 覆盖 "<<z; 29 count++; 30 z = i; 31 } 32 else if((i!=x&&i<x&&z<i)||(i!=x&&i<x&&z>=x)) 33 { 34 table[z]=table[i]; 35 table[i]=-1; 36 // cout<<"把索引 "<<i<<" 覆盖 "<<z; 37 count++; 38 z=i; 39 } 40 }while(table[i+1]!=-1&&(i+1)!=b); 41 42 cout<<count<<endl; 43 } 44 45 };
所以，对于新的问题的思考，不能分立地思考，考虑一个种类的元素同时也需要考虑是否会对其他类造成影响。
1.竞赛树:
赢者树，适用于有序的序列要求中，修改和查询操作多的问题。代表性的问题是装箱问题。赢者树的数据结构为二叉树，相对于二叉树的节点，会多一个本次赢者的域，存储此节点的赢者。每一个子树都记录此轮比赛的赢者。根节点记录总冠军。这样，这样的数据结构就能通过节点值直接检索到最小或最大的外部节点处，从而进行修改。当赢者树产生了修改时，需要对路径上从根节点到外部节点的所有节点进行修改。或者到一次必输的节点为止。赢者树的初始化可以从右孩子节点开始，右孩子的父节点一定能够进行比赛。这是完全二叉树的特点决定的。
输者树，是对赢者树的优化，可以比赢者树少一些复杂度。当问题只会修改总冠军时会比赢者树效率高很多，因为，输者直接记录在节点处，子节点的信息不会被赢者的信息覆盖，可以更快地完成树地更新。
2.搜索树:
搜索树也是一种二叉树，局部特征为：任何一个节点包括根节点在内，左子树的关键字大小于根节点，根节点小于右节点。这样，当查找一个元素的时候，只需要通过判断节点值的相对大小就就可以一路深入到叶子节点找到目标元素。插入时，只需要沿着相同的路径下潜最后插入到合适位置即可。
但是如果想要查找中位数或者顺序第n位呢？可以在节点处增加一个域，标记的内容为该节点左子树的size这样就可以利用这个值作为检索工具，快速地找到顺序第n个元素。
当二叉搜索树删除的时候，如果删掉了一个存在左右子树的节点，会需要给左右子树一个交代。怎么办呢？注意到空间位置上，被删除节点正下方的叶子节点正好比左子树根节点大，比右子树的根节点小，因此把这个叶子节点拿过来就能补上空位了。这便是索引搜索二叉树。
在应用上可以在直方图的频数统计上加速过程。首先，当将数据插入二叉搜索树，然后利用二叉搜索树的前序遍历的有序性，将其顺序输出，将极大地方便统计。
3.平衡搜索树：
平衡二叉树是一种不会“畸形”的二叉搜索树。平衡二叉树的任意一个左右子树高度差不会超过1，这就意味着，这种二叉树会保持logn的高度，同时也就意味着稳定的logn的搜索复杂度。
搜索，与搜索树是一样的。
平衡二叉树的插入，会牵扯到不平衡的问题。如果不平衡，会导致四种不平衡LL,LR,RL,RR，由于对称性，事实上只有两种不平衡。LL是由第一个不平衡节点的左左子树高度增一导致的。此时，左右子树与右子树的高度相同，而左左子树比他们都高1，那么只需要将左右子树和右子树放到同一高度，并且将左左子树进行修剪即可。具体来说，首先需要将LL，L，A（首不平衡节点），R连成一条链，然后将LL上移，R下移，L成为新的中心，然后将A的父节点接到L上方，断开的LR接到A左子树位置。至此便完成了一次LL翻转。新的节点中，L作为根节点，平衡因子为0。实现了平衡。如果是LR型，是由第一个不平衡节点的左右子树导致的，此时左右子树比左左子树和右子树均高一。此时LR的两个子树LRL,LRR中一定有一个高度为h,一个为h+1,而LL,R均为h,此时需要将C转移到L和A之间，然后将左右子树分别接到L的右子树和A的左子树，这样高度为h,或h+1的节点LL,LRL,LRR,R就都在同一起点处了，至此，达到新的平衡，平衡因子可能为1,-1,0完成了LR翻转。
原文：https://www.cnblogs.com/PRCdefender/p/13956751.html
