一、二叉树
1、基本概念
树(tree )是n ) n=0)个节点的有限集合，只有一个根节点，子树的数量没有限制，但一定不想传递。 树的定义是亚递归的。 节点度—节点拥有的子树的数量。二叉树(binary tree )是指树中节点度在2以下的有序树，是最简单最重要的树。
二叉树的递归定义是，二叉树是空树，或者根节点和两棵树不相交，分别是由叫做根的集中发卡和右子树组成的非空树； 集中发卡和右边那棵树也是二叉树。
没有父节点的节点称为根节点，图中f为根节点，c为a和d的父节点，a、d、h、g相互为兄弟节点，没有子节点的节点称为叶节点或叶节点，a、b、h、m表示
总结：二叉树可以是空树(n=0)。 二叉树的特征：每个节点最多两个子树、集中发卡、右子树(互不相交)； 集中发卡和右边那棵树有顺序； 即使树中的某个节点只有一个子树，也必须区别它是集中发卡还是右子树。
2、树的三个重要概念：高度（Height）、深度（Depth）、层（Level）
3、树的特殊类型
满二叉树：如果一棵树只有度0的节点和度2的节点，且度0的节点在同一层次上，则该二叉树为满二叉树。 完全二叉树：一种深度为k，有n个节点的二叉树，只有各个节点在深度为k的全二叉树中一一对应编号从1到n的节点时，才称为完全二叉树。 左斜树(所有节点仅由集中发卡的右斜树)所有节点仅由右子树集中)完全二叉树的特征)叶子的节点只出现在最下层或下一下层； 最下层的叶子节点集中在树的左部； 相同节点数的二叉树具有最小的完全二叉树深度。 二叉树的特征：所有树枝都有集中发卡和右边的树，所有叶子的节点都在最下层； 二叉树必须是完整的二叉树，反之不一定成立。
4、二叉树的存储
是基于指针或参照的二叉树状记忆法和基于序列的逐次记忆法。1 )顺序存储
是利用一维数组存储二叉树的节点，节点的存储位置是数组的下标索引。
可见，完全二叉树适合采用顺序记忆结构。 如果不是完全二叉树，记忆区域的一部分就会浪费，极端的情况下，右斜树就会超级浪费。
2 )链式存储二叉树在每个节点有两个孩子，因此将节点的数据结构定义为一个数据和两个指针字段。
总结：二叉树有两种记忆方式，分别是顺序记忆和连锁记忆。 顺序记忆适用于完全二叉树，非完全二叉树的顺序记忆会导致空间的相对浪费，因此转移到链式记忆。 相对来说，链式存储法是我们经常使用的。
5、二叉树的遍历
经典方法：前相遍历、中相遍历、后相遍历。 此外，还有分层遍历。 每个节点遍历n个节点一次，遍历的时间复杂度都是o(n )。
前顺序扫描(根左右) A-B-D-E-C-F中顺序扫描)左根右) D-B-E-A-F-C后顺序扫描)左右根) D-E-B-F-C-A前中后顺序扫描也是树的深度优先搜索) DFS )
分层遍历(每个高度访问一个) A-
gt;B->C->D->E->F层次遍历也可以看做树的宽度优先搜索（BFS）；代码实现此处先不描述，可另行查找理解，递归法，迭代法处理等。
小结：已知前序和中序遍历，或者已知中序和后序遍历都可以确定二叉树。前序遍历第一个访问的根节点，中序遍历根节点在中间，后序遍历最后访问根节点。
二、二叉查找树（二叉排序树）
二叉查找树要求，在树中的任意一个节点，其专注的发卡中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。二叉查找树最大的特点就是，支持动态数据集合的快速插入、删除、查找操作。特别是中序遍历二叉查找树，可以输出有序的数据序列，相当于升序排列，时间复杂度是 O(n)，非常高效。因此，二叉查找树也叫作二叉排序树。
三、散列表和二叉查找树区别
第一，散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。
第二，散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。
第三，笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为发嗲的柜子冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上发嗲的柜子函数的耗时，也不一定就比平衡二叉查找树的效率高。
第四，散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。
最后，为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。
综合这几点，平衡二叉查找树在某些方面还是优于散列表的，所以，这两者的存在并不冲突。我们在实际的开发过程中，需要结合具体的需求来选择使用哪一个。
四、红黑树
1、红黑树特点：
根节点是黑色的； 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；2、红黑树意义：
红黑树是一种平衡二叉查找树。它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的。
红黑树的高度近似 log2n ，所以它是近似平衡，插入、删除、查找操作的时间复杂度都是 O(logn)。因为红黑树是一种性能非常稳定的二叉查找树，所以，在工程中，但凡是用到动态插入、删除、查找数据的场景，都可以用到它。不过，它实现起来比较复杂。
小结：散列表：插入删除查找都是O(1), 是最常用的，但其缺点是不能顺序遍历以及扩容缩容的性能损耗。适用于那些不需要顺序遍历，数据更新不那么频繁的。跳表：插入删除查找都是O(logn), 并且能顺序遍历。缺点是空间复杂度O(n)。适用于不那么在意内存空间的，其顺序遍历和区间查找非常方便。红黑树：插入删除查找都是O(logn), 中序遍历即是顺序遍历，稳定。缺点是难以实现，去查找不方便。其实跳表更佳，但红黑树已经用于很多地方了。
** 3、红黑树的平衡调整：**调整的过程包含两种基础的操作：左右旋转和改变颜色，相对比较复杂，此处不过多描述。