树
树
树是由一个个节点组成的，最上层的节点叫做根节点，节点可以衍生出节点，相互之间是父子关系，同样，属于同一个父节点的叫兄弟节点，如果一个节点没有子节点，那么这个节点叫叶子节点或者叶节点，注意，树有一个很明显的特征：任意三个及以上的节点都不能形成闭合，即同一层的节点不连通，兄弟节点之间不能共享节点
树还有以下几个概念
注意，深度和高度都从0开始数起
有一个小窍门，就是类比“高度”“深度”“层”这几个名词在生活中的含义。在我们的生活中，“高度”这个概念，其实就是从下往上度量，比如我们要度量第 10 层楼的高度、第 13 层楼的高度，起点都是地面。所以，树这种数据结构的高度也是一样，从最底层开始计数，并且计数的起点是 0。
“深度”这个概念在生活中是从上往下度量的，比如水中鱼的深度，是从水平面开始度量的。所以，树这种数据结构的深度也是类似的，从根结点开始度量，并且计数起点也是 0。
“层数”跟深度的计算类似，不过，计数起点是 1，也就是说根节点位于第 1 层。
二叉树（Binary Tree）
二叉树，每个节点最多只能有两个子节点。
编号2这种全部排满的，叫做满二叉树，编号3这种除了最后一层，其它层都排满了，并且最后一层的叶子节点都连续排列（即叶子节点之间没有空位）的叫做完全二叉树。
怎样存储一棵二叉树
1.链表法，大部分情况都会使用这种方法存储二叉树
2.数组法
为什么完全二叉树最后一层的叶子节点不能中断呢？因为完全二叉树这个概念是为了省内存提出的，即数组只浪费掉第一个元素的空间，其他全部占满，所以最后一层的叶子节点们必须是排满的，这样在数组中就会表现成连续填满，数组只会浪费第一个元素的空间。
数组法中，如果某个结点的编号是x，那么其左节点的编号是 2 * x，右节点是2 * x + 1，父节点的编号是x / 2（如果是右节点，则去小数取整）。
一般为了方便，会把根节点放在下标为1的空间，所以会浪费下标为0的空间。
而如果数组来存储非完全二叉树，那么势必会造成部分空间空档，会浪费一些内存
二叉树的遍历
经典的方法有三种，前序遍历、中序遍历和后序遍历。其中，前、中、后序，表示的是节点与它的左右子树节点遍历打印的先后顺序。
前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。
实际上，二叉树的前、中、后序遍历就是一个递归的过程。比如，前序遍历，其实就是先打印根节点，然后再递归地打印左子树，最后递归地打印右子树。并且我们可以由图看出，每个节点都只会被最多访问两次，所以只有2n，不存在n的高阶，即时间复杂度是O（n）。
二叉查找树（Binary Search Tree）
二叉查找树，任意一个节点a的左子树的每个节点的值都要小于节点a，右子树的每个节点的值都要大于节点a，并且不允许有重复的值。
二叉查找树支持查找，插入，删除操作
①二叉查找树的查找是这样的：我们把当前节点取出来和要查找的节点比较，如果不等于，那么要是查找的节点比当前节点小，就进入到当前节点的左子节点，否则进入右子节点，就这样一直找下去，直到找到或者当前节点为空时停止，返回找到的节点或者null。
②二叉查找树的插入操作
二叉查找插入是这样的：当当前节点比要插入的元素大，并且当前节点的左子节点为空，就插入，如果不为空，就继续按这个规则找下去，直到找到有空的，同理，如果当前节点比要插入的元素小，并且当前节点右子节点为空，就插入，否则继续这样找。
③二叉查找树的删除操作
由于一个节点的子节点情况有三种，所以我们要分情况讨论
第一种情况，就是如果要删除的节点没有子节点，那直接父节点指向被删除节点的指针置为空即可。
第二种情况，如果要删除的节点有一个子节点，那么由于左子树全部小于被删除的节点，右子树全部大于被删除的节点，所以父节点必定大于被删除节点的左子树的所有节点，同理，小于被删除节点的右子树的所有节点，那么我们只要将父节点的指针跳过被删除的节点，去指向被删除的节点的子节点即可。
第三种情况，如果要删除的节点有两个节点，会比较麻烦，我们先看被删除的节点当前是怎样的状态，该节点的父节点必定大于或者小于被删除的节点，以及被删除节点的所有子树，而该节点的左右子树，一个是所有节点小于被删除的节点，一个是所有节点大于被删除的节点。而我们如果要删除了目标节点，那么肯定还要保持树的规则不变，而且不能破坏结构，所以我们可以想出这样一种删除节点的方法：
首先，我们需要在删除节点后，用另一个合适的节点来填补这个空缺，保持树的结构不被破坏，然后这个前来填补的节点要满足以下条件：
比被删除的节点的左子树的所有节点大，比被删除的节点的右子树的所有节点小。
于是我们按上述思路就找到了合适的节点，即被删除的节点的右子树中的最小节点，将它替换到被删除节点的位置。
实际上，关于二叉查找树的删除操作，还有个非常简单、取巧的方法，就是单纯将要删除的节点标记为“已删除”，但是并不真正从树中将这个节点去掉。这样原本删除的节点还需要存储在内存中，比较浪费内存空间，但是删除操作就变得简单了很多。而且，这种处理方法也并没有增加插入、查找操作代码实现的难度。
二叉查找树除了以上的三个操作，还有其他的操作，可以支持快速地查找最大节点和最小节点、前驱节点和后继节点，而且还有一个重要的特性，就是中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 O(n)，非常高效。因此，二叉查找树也叫作二叉排序树。
支持重复数据的二叉查找树
很多时候，在实际的软件开发中，我们在二叉查找树中存储的，是一个包含很多字段的对象。我们利用对象的某个字段作为键值（key）来构建二叉查找树。我们把对象中的其他字段叫作卫星数据。前面我们讲的二叉查找树的操作，针对的都是不存在键值相同的情况。那如果存储的两个对象键值相同，这种情况该怎么处理呢？
我们让二叉查找树中每一个节点不仅会存储一个数据，因此我们通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。
平衡二叉查找树
严格来说，平衡二叉树中，每个节点的左右子树，高度相差不超过1。完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。
严格来说，平衡二叉查找树则是满足了二叉查找树特点的平衡二叉树。但是很多平衡二叉查找树其实并没有严格符合上面的定义（树中任意一个节点的左右子树的高度相差不能大于 1），比如我们下面要讲的红黑树，它从根节点到各个叶子节点的最长路径，有可能会比最短路径大一倍。
发明平衡二叉查找树这类数据结构的初衷是，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。所以，平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。
所以，如果我们现在设计一个新的平衡二叉查找树，只要树的高度不比 log2n 大很多（比如树的高度仍然是对数量级的），尽管它不符合我们前面讲的严格的平衡二叉查找树的定义，但我们仍然可以说，这是一个合格的平衡二叉查找树。
红黑树
平衡二叉查找树中最常用到的就是红黑树。一颗红黑树只有红黑两种节点，并且需要满足以下条件：
1.根节点是黑节点。
2.每个叶子节点都是黑色的空节点（NIL），也就是叶子节点不存储数据。
3.任意相邻节点不能同时为红色，也就是红色节点之间是被黑色节点隔开的。
4.每个节点，从该节点到达其可以到达的叶子节点的所有路径，都包含相同数目的黑色节点。
红黑树是近似平衡的，平衡二叉查找树的初衷是为了解决二叉查找树在动态更新时因为变得不平衡而导致的性能退化问题，所以，平衡可以理解为性能不退化，近似平衡可以理解为使性能退化得不太严重。
递归树
对于一些求复杂度较难的算法，比如归并和快排这些，可以借助递归树来更简便地分析递归算法的时间复杂度。
二叉查找树对比散列表的优势
第一，散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。
第二，散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。
第三，笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。
第四，散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。
最后，为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。