二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2i-1个结点；深度为k的二叉树至多有2k-1个结点；对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
1、一颗树深度为h，最大层数为k，深度与最大层数相同，k=h;
2、叶子数为2h;
3、第k层的结点数是：2k-1;
4、总结点数是：2k-1，且总节点数一定是奇数。
1、具有n个结点的完全二叉树的深度[log2]+1（注：[ ]表示向下取整）
2、如果对一棵有n个结点的完全二叉树的结点按层序编号, 则对任一结点i (1≤i≤n)有
（1）如果i=1, 则结点i是二叉树的根, 无双亲;如果i>1, 则其双亲parent (i) 是结点[i/2]
（2）如果2i>n, 则结点i无左孩子, 否则其左孩子lchild (i) 是结点2i
（3）如果2i+1>n, 则结点i无右孩子, 否则其右孩子rchild (i) 是结点2i+1
1.本身首先是一棵二叉搜索树。
2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）。
1、结点是红色或黑色。
2、根结点是黑色。
3、所有叶子都是黑色。（叶子是NIL结点）
4、每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
5、从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：
1、根结点至少有两个子女；
2、每个非根节点所包含的关键字个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；
3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：┌m/2┐ <= k <= m ；
4、所有的叶子结点都位于同一层。
B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用。一棵m阶的B+树定义如下:
(1)每个结点至多有m个子女;
(2)除根结点外，每个结点至少有[m/2]个子女，根结点至少有两个子女；
(3)有k个子女的结点必有k个关键字。
B+树的查找与B树不同，当索引部分某个结点的关键字与所查的关键字相等时，并不停止查找，应继续沿着这个关键字左边的指针向下，一直查到该关键字所在的叶子结点为止。
B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；
B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）。
1、根节点不包含字符，除根节点外每一个节点都只包含一个字符；
2、从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；
3、每个节点的所有子节点包含的字符都不相同。
1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(Tabulation Machine)上的贡献。
它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。
这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，
然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
插入排序(Insertion Sorting)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，
无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，在有序表中从后往前进行比较，
将它插入到有序表中的适当位置，使之成为新的有序表。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，
每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
将两个的有序数列合并成一个有序数列，我们称之为"归并"。
归并排序(Merge Sort)就是利用归并思想对数列进行排序。根据具体的实现，归并排序包括"从上往下"和"从下往上"2种方式。
1. 从下往上的归并排序：将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并；得到若干个长度为2的有序数列，再将这些数列两两合并；得到若干个长度为4的有序数列，再将它们两两合并；直接合并成一个数列为止。这样就得到了我们想要的排序结果。(参考下面的图片)
2. 从上往下的归并排序：它与"从下往上"在排序上是反方向的。它基本包括3步：
① 分解 -- 将当前区间一分为二，即求分裂点 mid = (low + high)/2;
② 求解 -- 递归地对两个子区间a[low...mid] 和 a[mid+1...high]进行归并排序。递归的终结条件是子区间长度为1。
③ 合并 -- 将已排序的两个子区间a[low...mid]和 a[mid+1...high]归并为一个有序的区间a[low...high]。
快速排序的基本思想是任取待排序序列的一个元素作为中心元素(可以用第一个，最后一个，也可以是中间任何一个)，习惯将其称为pivot，枢轴元素；
将所有比枢轴元素小的放在其左边；
将所有比它大的放在其右边；
形成左右两个子表；
然后对左右两个子表再按照前面的算法进行排序，直到每个子表的元素只剩下一个。
可见快速排序用到了分而治之的思想。
将一个数组分成两个数组的方法为：
先从数组右边找到一个比枢轴元素小的元素，将数组的第一个位置赋值为该元素；
再从数组的左边找到一个比枢轴元素大的元素，将从上面取元素的位置赋值为该值；
依次进行，直到左右相遇，把枢轴元素赋值到相遇位置。
1.首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端
2.将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1
3.将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组
注意:升序用大根堆，降序就用小根堆(默认为升序)
1.确定待排数据的范围
2.确定扩展数组的大小，为数据最大范围+1
3.求出每个元素的出现个数
4.计算小于等于每个元素的元素个数
5.对待排元素倒序进行排序
1、设置一个定量的数组当作空桶；
2、设置桶的区间范围（区间跨度=（最大值-最小值）/（桶的数量+1））
3、遍历输入数据，并且把数据一个一个放到对应的桶里去；
4、对每个不是空的桶进行排序；
5、从不是空的桶里把排好序的数据拼接起来。