二叉排序树

二叉树查找

前言

有序线性存储表(顺序存储)，在查找方面有效率的优势，但是在插入和删除方面，却选哟花费大量时间。为了照顾插入和删除的效率，同时实现高效率的查找算法，我们引入了二叉树。

二叉排序树

二叉查找树又称之为二叉排序树，它可以为空树，也可以是具有以下特征的二叉树

• 若左子树不空，则左子树上所有结点的值均小于它根节点的值
• 若右子树不空，则右子树上所有结点的值均大于它根结点的值
• 左右子树也为二叉树
• 没有键值相等的点

（越往左越小）

查找

从某node开始查找，如果目标值小于结点，则往左查找；如果目标值大于结点，往右查找。

一直找到叶子结点没有找到，返回false

//伪码 使用递归
public boolean get(Node x, int data) {
    if (x == null) // 一直找到叶子节点，还没有找到就返回false
    return false;
    if (data < x.data) // 一条路径查找
    return get(x.left, data);
    else if (data > x.data) return get(x.right, data);
    else // 如果找到就返回true
    return true;
  }

可以得知查找一个值为固定的一条路线，效率较高（理论上100的数据量，找到目标值最多需要7次）

插入

在查找的基础上，找到叶子结点

• 如果插入的值等于叶子结点，返回false
• 如果插入值大于叶子结点，生成该叶子节点的右侧子树（反之亦然）

删除

请神容易送神难，查找到目标结点容易。若是目标结点拥有子孙后代，删除该结点，就会让子孙树游离，原本的对应的关系不正确了。

删除结点有以下几种情况

1. 叶子结点
2. 仅有左或右树结点
3. 左右树都有的结点

第一种情况

直接查找到该结点删除

第二种情况

查找到目标结点，其子树替补该位置

第三种情况

删除方法主要的概念是找删除结点前驱结点替换的方法（后继结点的方法也雷同）

• 找到删除结点前驱结点中数值最接近的结点childNode（左树值最大结点）
• 目标结点的值 = childNode值
• 删除childNode(如果有且仅仅会有左子树，替补childNode位置)

总结

二叉树查找的性能取决于该树的形状，其中比较值为目标结点所在的层数（深度），时间复杂度为：O（logn）

在极度极端情况下，二叉树仅仅只有左树（或者右树），相当于遍历线性表，即顺序查找，时间复杂度为：O(n)

因此我们更希望二叉树是一个平衡的树，即引出了平衡二叉树

平衡二叉树（AVL树）

平衡二叉树：属于一种二叉排序树，其中每一个结点的左子树和右子树的高度差最多为1

名词解释

平衡因子BF(balance factor)：二叉树上结点左树的高度减去右树的高度（0，-1，1）

最小不平衡树：距离插入结点最近的，平衡因子绝对值大于1的结点的子树

原理

• 插入是否破坏平衡？
  • 若否 插入
  • 若是
    1. 找出最小不平衡树
    2. 在不破坏二叉树特性的情况下，调整最小不平衡树中各节点的连接关系
    3. 进行旋转，成为新的平衡树