树
树描述了一种一对多的关系，是一种递归形式的数据结构，每个节点（除了根节点）都由父节点，和子节点（除了叶子节点）。一个父节点可以对应多个子节点。最常见的是二叉树，一个父节点最多有两个子节点。
树的高度：根节点最大，最长路径的叶子节点为0。
树的深度：根节点为0，最长路径的叶子节点为最大。
层：层数为深度+1，根节点为1层。
二叉树
- 类型
1. 满二叉树：除了叶子节点，每个节点都有2个子节点的二叉树。
2. 完全二叉树：除了最后一层，其他层节点个数达到最大，最后一层叶子节点全部靠左排列。
- 存储方式
1. 链式存储：指针或引用。
2. 顺序存储：数组，对于节点i，左子树位置2i，右子树位置2i+1。
- 遍历
1. 前序遍历：父->左->右
2. 中序遍历：左->父->右
3. 后序遍历：左->右->父
前中后说的是父节点的位置。
二叉查找树
定义
对于二叉树中任意节点，左子树的所有值都小于该节点，右子树的所有值都大于该节点。
中序遍历二叉查找树既可以得到从小到大的有序数列。遍历的时间复杂度是O(n)。
查找
类似于二分查找，从根节点开始进行比较，如果小于根节点从左子树里查找，如果大于根节点从右子树里查找，递归进行，直到找到相等节点。时间复杂度与树的高度成正比，平衡二叉树为O(logn)，极端情况下会退化成链表O(n)。
插入
从根节点开始比较
IF 小于节点
IF 左子树为空
插入左子节点位置
ELSE 左子树不为空
与左子节点进行比较
IF 大于节点
IF 右子树为空
插入右子节点位置
IF右子树不为空
与右子节点进行比较
删除
分为三种情况：
- 要删除的节点没有子节点：直接删除该节点。
- 要删除的节点只有一个节点：直接指向子节点。
- 要删除的节点有两个节点：指向右节点，并将左节点插入到右节点的不为空的左子节点中。
inline void BinaryTree<elemtype>::remove_root()
{
if(!_root) return;
BTnode<elemtype> *tmp = _root;
if(_root->_rchild)
{
_root = _root->_rchild;
if(!_root->_lchild)
//右子树没有左子树，直接将根节点左子树挂上
_root->_lchild = tmp->_lchild;
else
//右子树有左子树，遍历寻找左子树中为空的左子节点，挂上
BTnode<elemtype>::lchild_leaf(tmp->_lchild, _root->_lchild);
}
else
_root = _root->_lchild;
delete tmp;
}
支持重复数据
两种解决思路：
- 每个节点上挂链，重复节点以链表形式存储。
- 将相同的节点插入到右子节点位置。
平衡二叉树
目的：
解决频繁插入删除操作下，二叉树变得极度不平衡导致退化为接近链表，性能急剧下降的问题。
定义：
是一个二叉搜索树并且任意节点的左右子树高度差不超过1。
例子：
AVL树，每次插入和删除后通过左旋右旋调整树的结构保持平衡。
红黑树
红黑树并不是严格的平衡二叉树，但是能够保证性能退化不严重。查找效率没有AVL高，但是相比每次插入删除的维护操作，维护成本比AVL低。
定义：
根节点为黑色。
所有叶子节点为黑色的空节点。
红色节点不会相邻。
每个根节点到叶子节点经过的黑色节点数相同。
红黑树的高度分析：
平衡二叉树的高度为logn，红黑树的高度可以做如下近似分析：
去掉所有的红色节点，剩下的黑色节点就是一个完全二叉树，高度为logn，加入红色节点后的高度最大为2logn。
红黑树的旋转操作需要看书补充。
递归树
画图分析时间复杂度。
网友评论