关于树的名词

节点、根节点、父节点、子节点、叶子节点、节点权、层、子树、树的高度、森林

二叉树

满二叉树
所有叶子节点都在最后一层，并且节点总数为2^n - 1，n为层数

完全二叉树
叶子节点都在最后一层或倒数第二层，且最后一层只有叶子节点

二叉树的遍历

前序遍历：先输出父节点，再遍历左子树和右子树
中序遍历：先遍历左子树，再输出父节点，再遍历右子树
后序遍历：先遍历左子树和右子树，再输出父节点

二叉排序树BST

二叉排序树/二叉查找树/二叉搜索树。

特点
1.左子树所有节点均小于根节点
2.右子树所有节点均大于根节点
3.左右子树也是二叉排序树

二叉树可以提高查询效率：O(logn)

平衡二叉树AVL

最重要的特性在于平衡，这使得我们能够在最坏情况下也保持O(logn)的时间复杂度实现查找（一个不具备平衡性的查找树可能退化成单链表，时间复杂度会到O(n)）

当二叉树的左右两棵子树的高度差超过1时，会对操作效率有影响。

平衡二叉树特点
1.任意节点的子树高度差均 >= 1
2.是二叉排序树

平衡二叉树的旋转

平衡因子 BF：左右子树高度差。BF > 1，则二叉平衡树失衡，需要进行旋转。

最小不平衡二叉树：距离插入节点最近的不平衡子树

当左子树比右子树高1以上，需要右旋
当右子树比左子树高1以上，需要左旋

举例：{3,2,1,4,5,6,7,10,9,8}的步骤
3 2 1 ，LL失衡，右旋 2 1 3
2 1 3 4 5 ，RR失衡，左旋 2 1 4 3 5
2 1 4 3 5 6 ，RR失衡，左旋 4 2 5 1 3 6
4 2 5 1 3 6 7 ，RR失衡，左旋 4 2 6 1 3 5 7
4 2 6 1 3 5 7 10 9 ，RL失衡，先右旋 4 2 6 1 3 5 7 9 10
再左旋 4 2 6 1 3 5 9 7 10
4 2 6 1 3 5 9 7 10 8 ，RL失衡，先右旋 4 2 6 1 3 5 7 9 8 10
再左旋 4 2 7 1 3 6 9 5 8 10
完毕

多路平衡查找树

2-3-4树是阶数为4的B树。

2-节点，包含 1 个元素和 2 个指针
3-节点，包含 2 个元素和 3 个指针
4-节点，包含 3 个元素和 4 个指针

红黑树

复杂度O(logn)

对于AVL树，平衡条件是：左右子树深度差<=1。而对于红黑树，平衡的条件是：左右子树深度差一倍以内。

红黑树规则

BST、AVL、红黑树 对比

BST树缺点：容易不平衡，在数据递增或递减时会退化为链表(logn --> n)，查询性能不佳。

AVL树缺点：完全平衡，查询效率高，但是在执行增删操作时，需要频繁变换树的结构。

红黑树：介于不平衡和完全平衡之间。通过每个节点有红黑两种颜色、从节点到任意叶子节点会经过相同数量的黑色节点等一系列规则，使得树的层数最大也只会有两倍的差距，这样既能提高插入和删除的效率，又能让树相对平衡从而有还不错的查询效率。从整体上讲，红黑树就是一种中庸之道的二叉树。