数据结构-树/平衡二叉树/二叉查找树/红黑树

2019年7月26日
前言：树是一种数据结构的组织方式，不同的数据组织方式在数据的增删改查方面性能上有差异。例如ArrayList增删慢，其时间复杂度O(n），修改查询快，时间复杂度为O(1)；LinkedList正好与ArrayList相反；而红黑树在增删改查的时间复杂度均为O(log(n))。接下来，是我对树的简单总结和理解。
全文缺少配图，有时间补上

概念理解

树：从直接前继和直接后继个数角度，可以这样定义， 0到1个直接前继，0到n个直接后继，其中n>=2。
节点：树就是由有限节点组成的一个具有层次关系的集合，数据就存在这些节点中。
根节点：最顶上的一个节点，没有父节点。
子节点：两个相连节点的关系。
叶子节点：某个节点下方没有任何分叉。
节点的高度：从某个节点出发，到叶子节点为止，最长简单路径上边的条数，称为该节点高度。
节点的深度：从根节点出发，到某节点边的条数，称为该节点的深度。

二叉树：至多有两个子节点的树，平衡二叉树、二叉查找树、红黑树都是一种特殊的二叉树。

平衡二叉树性质：

（1）树的左右高度查不能超过1；
（2）任何往下递归的左子树和右子树，必须符合第一条性质；
（3）没有任何节点的空树或只有根节点的树也是平衡二叉树。

二叉查找树性质：

（1）对于任意节点来说，它的左子树上所有节点的值都小于他，而他的右子树上所有节点都大于他。
遍历所有节点的常用方式有三种：前序遍历、中序遍历、后序遍历。
（1）在任何递归子树中，左节点一定在右节点之前遍历。
（2）前序、中序、后序，仅指根节点在遍历时的为止顺序。
前序遍历顺序：根节点、左节点、右节点；
中序遍历顺序：左节点、根节点、右节点；
后序遍历顺序：做节点、右节点、根节点；
二叉查找树由于数据不断增加或删除容易失衡，因此为了保持二叉树重要的平衡性，有很多算法实现，比如AVL树、红黑树等

AVL树：

AVL树是一种平衡二叉查找树，在增加或删除节点后通过树形旋转重新达到平衡。
右旋，以某个节点为中心，将它沉入当前右子节点的位置，而让当前的左子节点作为新树的根节点，也称为顺时针旋转。
左旋，以某个节点为中心，将它沉入当前左子节点的位置，而让当前右子节点作为新树的跟节点，也称为逆时针旋转。

红黑树：一种特殊的二叉查找树

与AVL树相比，红黑树并不追求所有递归子树的高度差不超过1，而是保证从根节点到叶子节点的最长路径不超过最短路径的2倍。
相比二叉查找树，有5个约束条件：
（1）节点只能是红色或黑色。
（2）根节点必须是黑色。
（3）所有NIL节点都是黑色的。NIL，即叶子节点下挂的两个虚节点。
（4）一条路径上不能出现相邻的两个红色节点。
（5）在任何递归子树内，根节点到叶子节点所有路径上包含相同数目的黑色节点。

总结即是“有红必有黑，红红不相连”，上述5个约束条件保证了：
（1）红黑树的新增、删除、查找的最坏时间复杂度均为O(logn);
（2）如果一个树的左子节点或者右子节点不存在，则均认定为黑色；
（3）红黑树的任何旋转在3次之内均可完成。（这个是怎么计算出来的？？？）

红黑树与AVL树的比较

这里还需更加详细分析两者的区别
面对频繁的插入和删除，红黑树更为合适；
面对低频修改、大量查询，AVL树更合适。