数据结构之树（一）

树，表示一对多的关系模型，比如父母和子女的关系，班级和学生的关系等

二叉树包括：

二叉树的存储：对于完全二叉树，由于其定义严格，可用层序编号顺序存储，对于一般二叉树，可用孩子表示法：二叉链表存储

二叉树的遍历：

通过不同遍历方法，可以得到二叉树的次序，同样，通过特定遍历方法的次序，可以确定一棵树
二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构

待研究

定义：每个节点的值都大于左子树任意节点，且小于右子树任意节点

删除操作：

平均情况：插入和查找性能都是$O(\log n)$
最坏情况：如果按照顺序或者逆序插入，会退化为链表，插入和查找性能都变为$O(n)$

性质：中序遍历结果为从小到大排列的序列

定义：在二叉排序树之上，限制任意节点的左右子树高度差最大为 1

为解决二叉查找树最坏情况退化为链表的性能问题，引入平衡二叉树，只要保持树的高始终小于$\log n$，则就能保证查找在最坏情况依然为$O(\log n)$

最小失衡树：在新插入节点向上查找，第一个不能平衡的子树

通过对最小失衡树的左旋或者右旋操作使树重新平衡。

2-3 树：有两种节点，2-节点和 3-节点
2-节点：包含一个元素和两个子节点
3-节点：包含两个元素和三个子节点

插入操作：
2-节点，2-节点直接变为 3-节点，树的高度不变
3-节点，多余节点向父节点移动，如果父节点是 2-节点，则父节点变为 3-节点，高度不变

当原来的树中所有元素都为 3-节点时，由上可知，根节点由一个 3-节点分化为 3 个 2-节点子树，树的高度加 1

由此可见，2-3 树是向上增长，插入操作最坏情况性能是$O(\log n)$，而且始终保持平衡，因此，查找性能依然为$O(\log n)$

红黑树：本质就是 2-3 树，用颜色代替 3-节点的功能，便于代码操作

所有的 3-节点拆分为 2 个 2-节点，用红色标注 2 个中较小的那个节点

红黑树的性质：

插入操作：通过左旋、右旋和颜色变换，实现平衡

五种情况：

红黑树和平衡二叉树比较：
增删方面：红黑树性能优于平衡二叉树，红黑树任何不平衡，都能在 3 次旋转内得到解决
查找方面：平衡二叉树优于红黑树，因为平衡二叉树是严格平衡的，而红黑树在最坏情况下（红黑相间的斜树），查找性能是$O(2\log n)$

4) 线索二叉树
线索二叉树：由于二叉链表存储的二叉树，有很多空指针的空间浪费，所以利用这些空指针存储节点的前驱或者后继，此时二叉树实际就变为一个双向链表