树（中）
二叉搜索（排序/查找）树
作用：为了进行二分查找，将数据构建在查找树中，相比与线性结构树的插入删除等动态操作更为方便。
定义
- 可以为空
- 若不为空，左子树的键值都小于根节点，右子树的键值都大于根节点。
- 左右子树都是二叉搜索树。
操作
- 增加
- 删除
删除过程略复杂，如果是叶子节点可以直接删除，如果有一个孩子，则直接让孩子替代原来的位置；如果有两个孩子，则选择左子树的最大值，或者右子树的最小值，来替代原来的位置
这是就转化成了一个孩子（没有孩子 ）的情况。
平衡二叉树
作用：对于同一个序列，如果根节点确定下来那么，整个搜索树也就去确定了，所以对于选定不同的根节点，构造出来的树的形状是不一样的，其查找效率也不同。
一种高效率的查找树是，左子树和右子树深度相近。
衡量指标：平衡因子。左右子树的高度差。要求：小于1；
平衡二叉树的高度能达到log2(n)？
h层高度的平衡二叉树，最少需要hn个节点。可以推出：hn = h(n-1) + h(n-2) + 1;可以看出，类似于斐期那比数列。得出：hn = f(h+2) -1;
可以推出：节点数为n的平衡二叉树，高度最大能达到log2(n)
平衡二叉树的调整
为什么需要调整？
当动态的删除/增加一个序列，适合最根节点的键值，必然会改变，所以会造成二叉树由平衡变为不平衡。
几个概念：
被破坏者：由于插入/删除一个节点，造成某个节点不在平衡（可能有多个节点被破坏，只考虑最底层的节点）。
破坏者：插入/删除的节点。
- R旋：破坏者在被破者的右子树的右子树上。
- L旋：破坏者在被破坏者的左子树的左子树上。
- LR旋：破坏者在被破坏者的左子树的右子树上。
- RL旋：破坏者在被破坏者的右子树的左子树上。
