list -> array可以转换,很好玩的一个结构

• 数组的值是下标表示, 关系，甚至可以表示数组森林

1. 降低树高度的方法，缓存？路径压缩 （缺点：）
2. 加权，让大树作为根，可以证明加权 logN

• 排序 每一种算法都是上一种的强化

1. 选择排序，选中最小值，比较 n^2/2 , 交换 n
2. 插入排序, 选中i元素，然后插入 index < i（二分查找）上 , 缺点是每次插入后后续都会进行位置的移动,最惨的是一个完全逆序的数组 思路：对于比较顺序的元素，是否性能更强?
3. 希尔排序的思想: 是插入算法的强化，乱序数组插入排序的时候交换的次数会很多，假设一个完全逆序数组，元素只能一个一个移动，希尔排序。思路： 如果使用不同增量，是否可以使比较次数变小
4. 归并和快速排序，都是分冶，但是一个递归在处理前，一个在处理后，这里提供了一个思路：如果在递归前处理，是否可以不使用额外空间
5. 快速排序的空间复杂度为logN，而并非1，因为来自递归，每次产生两个子问题，因此需要logN, 空间复杂度不能只考虑单个调用，栈深度也要考虑到

• 一个重要的性质，稳定性，排序后能保留相对位置，比如一个已经按照时间排序好的数组，如果你按照别的列进行排序，可能时间就不顺序了。 目前来看，插入排序和归并排序是稳定的

证明比较排序不能小于 nlogn的方法

构造了一棵比较树，比较次数是非页节点，排列组合方式是叶子节点，下界即为高度, logN! => NlogN

• 消除边界条件

1. 条件上推
2. 使用max，min，代替
3. 默认值
4. 归约思想, 把一类事物归于另一类

关联条件元素修正应该尽量靠在一起

树

2 - 3 树， 向上生长， 性质：

红黑树呢？ -> 其原理在于：3 节点可以视为 两个节点相连，连接是红连接 如果把红黑树 红链 化成3节点就是一棵 23树， 旋转的原理，rotate传进来实际上是两个节点，如果被指向的节点是