一文精通如何使用二叉树

一、树

一些基本概念有：

节点、父节点、子节点、兄弟节点、根节点、叶子节点；

高度(从叶子节点往上)、深度(从根节点往下0 ^ (n-1) )、层(从根节点往下1~n)；n为层数；

二、二叉树

一些基本的概念：

• 左子节点、右子节点；二叉树要求每个节点最多只能有两个子节点，但并不要求必须有两个子节点，单独有左子节点或者右子节点都是可以的；
• 满二叉树，是指所有叶子节点都在最底层，除了叶子节点以外，每个节点都有左右两个子节点；
• 完全二叉树，是指所有叶子节点都在最底下两层，最后一层的叶子节点是从左到右依次排列的，中间不能有空缺，其它层节点个数都要达到最大，不能有空缺；
• 存储方法有链式存储法、顺序存储法；

大部分二叉树都可以使用如下链式存储法来进行表示，必然要左右节点空间来指向各自的左子节点和右子节点；

二叉树的链式存储

顺序存储法则是利用一个数组，将当前节点存放在下标为i的地址中，那么左子节点就存放在2i的地址中，右子节点存放在2i+1的地址中；反过来，已知某个节点位置为k，那么它的父节点位置就是k/2；但是当二叉树不是一颗完全二叉树的时候，就会比较浪费数组存储空间；因此，当二叉树为完全二叉树的时候，采用顺序存储是最优的；

完全二叉树的顺序存储

非完全二叉树的顺序存储

• 遍历分为前序遍历、中序遍历和后序遍历；

前序遍历，先自己，再左边，最后右边；

中序遍历，先左边，再自己，最后右边；

后续遍历，先左边，再右边，最后自己；

三、二叉查找树

在二叉树的基础上，满足如下条件：对于任意一个节点，其左子树上的每个节点值都要小于当前节点的值，其右子树上的每个节点值都要大于当前节点的值；

查找，目标元素target和当前节点比较，如果比当前节点小那么就在左子树中继续查找，反之则在右子树中查找；

插入，目标元素target和当前节点比较，如果比当前节点小并且当前节点没有左子树，那么作为左子节点插入，如果有左子树，那么继续往左遍历；如果比当前节点大并且当前节点没有右子树，那么作为右子节点插入，如果有右子树，那么继续往右遍历；

删除，先找到目标元素，如果目标没有子节点，直接将其删除即可；如果目标有子节点（左右子节点都可），那么将目标节点的父节点指向目标节点的子节点即可；如果目标节点同时拥有左右子树，那么就需要在右子树中找到最小值替换当前节点；（如果想要提高删除的性能，我们还是可以采用标记删除法，以空间换时间）

二叉查找树的删除操作

• 查找最大值和最小值；
• 寻找给定元素的前驱和后继节点；
• 中序遍历输出完全有序的数列，时间复杂度O(n)，相较于原先讲过的八大排序算法来说，算是最好的排序算法了；
• 重复数据的存储；

相同值存放在同一个节点；

相同值存放在右子树；但是要求在查找和删除的时候，一定要遍历到叶子节点才能找到所有相同的元素；

• 时间复杂度分析，在最坏的情况下，二叉查找树退化为链表，那么所有操作的时间复杂度都是O(n)，但是在完全二叉树时，时间复杂度取决于树的高度，就是O(logn)；

四、平衡二叉查找树

如何让二叉查找树尽量保持平衡，让时间复杂度维持在O(logn)，这是平衡二叉查找树需要做的事情。那什么样子的二叉查找树可以被称为平衡的二叉查找树呢？

严格的定义就是：任意一个节点的左右子树的高度相差不能大于1；比如AVL树，这就是一种高度平衡的，完全符合平衡二叉树定义的。

但是，比较严格的平衡二叉树实现起来有些复杂，需要耗费过多的资源在平衡高度差不超过1这个条件上面，反而矫枉过正了。因此，我们只要能设计出一种二叉查找树，使得所有节点的左右子树看起来相对均衡，那么也可以将它称为符合要求的平衡二叉查找树，比如下面的红黑树。

五、红黑树

红黑树是一种不严格的平衡二叉查找树，它具有以下要求：

• 根节点是黑色的；
• 每个叶子节点都是黑色的空节点，不存储数据；
• 任何上下相邻的节点都不能同时为红色，红色节点是被黑色节点隔开的；
• 每个节点到到其所有叶子节点的路径都包含相同数目的黑色节点；
• 插入的节点必须是红色的，新插入的节点都是放在叶子节点上的；

红黑树在插入节点时，如果父节点是黑色的，那么直接插入就行；如果插入的节点是根节点，那么将它改为黑色即可；除此之外的任何情况，都会破坏如上红黑树的要求，此时就需要通过左旋、右旋或者改变颜色才能重新符合红黑树的要求。红黑树的实现过程和平衡过程都比较复杂，一般了解即可。

红黑树具有稳定的性能，在插入、删除和查找时都能稳定在O(logn)，同时不会浪费太多资源进行平衡的操作，所以在工业运用上，比严格的平衡二叉查找树要更加地受欢迎。

六、递归树

递归树主要可以用来分析复杂算法的时间复杂度；比如原先说过的归并排序，时间复杂度是O(logn)，这个使用递归树怎么分析呢？

归并排序的递归树

归并排序的过程就是每次分解都是1/2，直至每个节点只有一个元素为止，然后从下往上进行相邻节点的归并排序，直至归并为一个数列。

分解的过程时间耗费比较小，因为可以利用数组随机访问的特性一分为二，所以时间可以记为常数C；

归并的时候每层都需要比较n个元素，所以时间复杂度为O(n)，假设树的高度为h，那么时间复杂度就是O(hn)，其中高度怎么计算呢？在满二叉树的时候，树的高度可以表示为logn，所以归并过程的时间复杂度就近似为O(nlogn)，那么整个分解和归并的时间复杂度就是O(C+nlogn)，去掉低阶，最终得到归并排序的时间复杂度就是O(logn)。

七、总结

二叉树比散列表的优势在哪里？

散列表中的数据是无序存储的，如果我们需要有序的数列，就必须先排序，时间复杂度取决于你用的排序算法以及无序数据的排列情况，但是肯定不会好于O(n)，但是二叉查找树，又称二叉排序树天然就是有序的，只要按照中序遍历输出即可，时间复杂度稳定为O(n)；

散列表有扩容操作，哈希计算操作，还会有冲突再散列的问题，其时间效率并不稳定；而平衡二叉树能让查找、插入和删除的时间复杂度能稳定在O(logn)；当数据量大的时候，平衡二叉树的优势和性能将会远超散列表；

散列表实现起来比较复杂，需要考虑散列函数的设计、装载因子的设计、扩容和缩容方案、冲突再散列如何解决等；而平衡二叉树只需要考虑平衡的问题，比较简单，方案也比较成熟。