数据结构学习笔记-排序/队/栈/链/堆/查找树/红黑树

排序：

插入排序：每次从剩余数据中选取一个最小的，插入已经排序完成的序列中

合并排序：将数据分成左右两组分别排序，然后合并，对每组数据的排序递归处理。

冒泡排序：重复交换两个相邻元素，从a[1]开始向a[0]方向冒泡，然后a[2]...当a[i]无法继续往前挤的时候说明前面的更小了，而且越往前越小(挤得越往前)

堆排序：构造最大堆，每次取走根结点（自然是最大的），再调用MAX-HEAPIFY算法(见后文的堆)恢复最大堆的性质，重复取走根结点

快速排序(对A[r]-A[n]进行排序):

1.从序列中选取一个元素作为主元并与A[n]交换，或者直接把A[n]作为主元

2.将序列划分为左中右三部分，主元在中间。left中任何元素都<=主元，right中任何元素都>主元。

具体划分方式为：将序列的A[r]-A[n-1]部分划分为三个依次相连的区域：left,right,未划分，在未划分的区域遍历，如果某元素比主元大不作处理，如果比主元小，则将此元素与right区的第一个元素交换，并将新的right区的第一个元素划给left区。遍历完毕够将A[n]与right区的第一个元素交换。

([left][right][未划分][主元]，也就是把未划分区域的元素不断移动到left区或保持不动变成right区的一部分)

3.对划分好的左右两部分分别排序，这样递归下去，直到某一部分的元素数量少于等于三个可以直接进行排序。

队栈链堆：

栈：先进后出的结构，push时栈顶升高，元素放入新栈顶；pop时取出栈顶元素，栈顶降低。

(循环)队列:先进先出的结构,top指向队首的位置，tail指向新元素要加入的位置(也就是队尾的后一个位置)。

enqueue时元素放入tail,tail循环后移；dequeue时取出top元素,top循环后移。

队列的容量比数组容量少一。(否则当top和tail相等时无法判断队列是空还是满)

链表:前一个元素指向后一个元素（后一个也可能指向前一个），经典操作插入，删除，搜索，可以在头元素之前尾元素之后加入哨兵元素以简化边界判断。

最大堆(最小堆同理):一颗完全二叉树，而且每个结点都是所在子树中的最大结点

最大堆MAX-HEAPIFY算法：当最大堆的根结点的值发生了变化，可能不再是整个树中最大的结点了，使用此算法可以维持最大堆的性质(每次和左右结点中最大的那个交换，递归下去，最终移动到合适的位置)

最大堆建堆(自下而上MAX-HEAPIFY)：从第max/2个结点(最后一个元素是此元素的孩子结点，此元素再往后的点都没孩子，自然都是最大堆)，从此结点依次往前调用MAX-HEAPIFY算法，可以保证从下到上的每个子树都是最大堆，那么整体也是最大堆。

用最大堆实现最大优先级队列：

1.取最大权重元素：A.First

2.移除最大权重元素:取出A.First,然后把A.Last移动到A.First并对新的A.First执行向下递归的MAX-HEAPIFY操作以维持最大堆性质。

3.插入元素：在最后面新增元素(成为新的A.Last)，对A.Last向着父结点方向递归交换上升到适合的位置。

4.增加A[i]的权重：A[I]向着父结点方向递归交换上升到适合的位置。

二叉查找树：

每个结点的KEY，都比其左子树的任意结点的KEY大，比其右子树的任意结点的KEY小。因此通过中序遍历可以从小到大顺序输出（中序遍历：先遍历左子树，再遍历父结点，最后遍历右子树）

查找:从父到子从上到下，想找更小的数往左拐(如果要找的数小于根结点，则一定在左子树中)。直到匹配，或者找到了NIL。

最大KEY值元素:顺着右子树的右子树的右子树……找到底，因为右子树总是比较大。

最小KEY值元素：同理，顺着左子树找到底。

后继（中序遍历中下一个遍历到的结点）:

1.如果结点有右子树，则后继是右子树RT的左下角(左中右,下一个遍历到的一定是RT的左子树的左子树的左子树的左子树。。。)

2.如果结点(设为c)不含有右子树,则一路向上找祖先，直到找到某个结点s,使得c在这个结点的左子树中（也就是说s的左孩子也是c的祖先，或者就是c），此时c的左子树刚遍历完毕即将遍历s，自然s就是c的后继了

前驱(和后继问题对称)

1.如果含有左子树，则一定是左子树的最大结点

2.如果没有左子树，则F所在的某颗右子树马上要被遍历了，找前驱顺着父节点往上找就是（直到找到某个结点S，使得S的右孩子也是F的祖先）

插入：

像查找一样从上到下根据和父结点大小的对比，选择左转还是右转，直到落到合适的空位上。

删除:

1.如果F没有孩子结点，直接删，什么都不影响

2.如果F有一个孩子结点，删除该结点，并且将它的孩子节点（C）连接到父结点（S）上

（这样并不会改变S的左子树所有结点比S小，右子树所有结点比S大的局面）

3.如果F有两个孩子结点，则把F的后继删除，然后用后继替换F(后继是右子树左下角，最多只有一个右孩子，用1或2的方式删了无影响；由于F和其后继大小相邻，替换后中序遍历依然从小到大，说明没有破坏查找树的性质)

红黑树:

根节点和最底下无数据的叶子结点(Nil结点)为黑色，任意父子结点不能同时为红（这样可以保证每个路径红的数量不大于黑），任意路径的黑结点数量相同（配合前面的性质，保证了最长的路径最多不超过最短路径的二倍，一种平衡策略）。插入删除操作都是 0(lnN), 且最多旋转三次

旋转：

分左旋和右旋。旋转改变某个结点和它的左孩子或右孩子的关系。因为改变上下的同时也改变了左右，因此不影响左<中<右的查找树性质。一定的旋转和变色操作可以恢复红黑树的性质。

左旋：结点F绕着右孩子R逆时针旋转90度，结果F变成了R的左孩子，R原来的左孩子分给了F的右边，F原来的父结点被R连上了。左旋导致了右孩子的右侧分支变短了。

右旋：结点F绕着左孩子L顺时针旋转90度，指针变更和左旋同理，导致左孩子的左分支变短了。

红黑树的插入：（插入的位置如同普通查找树，每次只插入红的，这样只破坏红色不相邻的性质）:

如果红黑树是空的：放入根结点的位置，变成黑色

如果父结点是黑的。不破坏性质。

之后以新结点的父结点是爷爷结点的左孩子为例；右孩子的情形与此对称：

1.父结点和叔父结点都是红的：

让父结点和叔父结点变黑，祖父变红，这样解决了父子同红的问题。如果恰好曾祖父为红，则递归向上解决问题。

2.父红，叔父黑，新结点是父结点的右孩子。则左旋父结点，这样父子左右关系颠倒，变成情况3

3.父红，叔父黑，新节点是父结点的左孩子。则右旋祖父结点（按照预设，父结点是祖父结点的左孩子）。此时父子双红的左分支高度降低，原来的父节点位置变低，跑到右侧。此时再交换原祖父结点和父结点的颜色，就左右均衡了。

删除

如果红黑树只有一个结点，直接删除；

如果删除的结点有两个孩子，则实际删除的是其后继，变成没有或者一个孩子的情况。

如果有一个孩子，则必定是黑结点红孩子，直接用孩子结点替代父结点并且把颜色变黑即可。

如果结点没有孩子且结点为红色，直接删除即可。

因此唯一需要讨论的就是要删除的结点为黑色而且没有孩子结点。

包含多种情况，使用变色旋转等技巧可以使树平衡。看了好久好久也没整理下来，不继续浪费时间了