一、二叉排序树（二叉搜索树BST）

1、概念与性质

• 1）只要且必须满足【左子树节点】<【根节点】<【右子树节点】就行
  • 那么注意：【平衡二叉树】与【二叉搜索树】关系
    • 前面学的【折半查找二叉树】=【平衡二叉树】，一定属于是【二叉搜索树BST】
    • 但是【二叉搜索树BST】不一定是【平衡二叉树】，它可以是任意形状

• 2）二叉搜索树的【中序遍历】一定得是【升序】！！！
  • 前面【折半查找二叉树】的笔记也学过，也是【中序遍历】是【升序】

• 3）数据结构的代码结构
  • 简单看一眼就行

2、BST的搜索过程

如图所示：

• 从根节点出发
• 要【搜索的关键字】小于【节点】，就往左边走
• 要【搜索的关键字】大于【节点】，就往右边走
• 直到查到为止
• 数据结构的代码结构
  • ​​​​​​​简单看一眼就行
  • 注意【循环查找】比【递归查找】省空间
    • 【循环查找】：【O(1)】
    • 【递归查找】：【O(h)】，h是该二叉搜索树树高

3、BST的插入

如图所示：（跟查找搜索一样）

• 从根节点出发
• 要【插入的关键字】小于【节点】，就往左边走
• 要【插入的关键字】大于【节点】，就往右边走
• 直到查找失败，找到NULL空节点为止

4、BST构造

还是按二叉搜索树的搜索、插入的逻辑

• 第一个数是根节点，往后都按插入逻辑一点一点构造就行了
  • 要【插入的关键字】小于【节点】，就往左边走
  • 要【插入的关键字】大于【节点】，就往右边走
• ​​​​​​​那么注意：
  • 【不同序列】可以构建【相同形状二叉搜索树】
  • 也可以构造【不同形状的二叉搜索树】

5、BST的删除

稍微比插入复杂一点点：

• 1、【叶子节点】可以直接删了

• 2、【非叶子节点】删除

  • 如果【它只有1个左子树、或1个右子树】

    • 直接让子树接上去就行

  • 如果【它有左右子树】

    • 1）要么选它【右子树下最小节点】接到它的位置，然后接替它的节点位置按【上面1、2情况】处理
    • 2）要么选它【左子树下最大节点】接到它的位置，然后接替它的节点位置按【上面1、2情况】处理

6、BST的【平均查找次数ASL】

1）【查找成功ASL】

• 记住ASL计算方式完全按【折半查找树ASL】计算方式，不会回去看笔记
• 【最好情况】：
  • 二叉搜索树BST是【平衡二叉树】时
  • 【时间复杂度】：【O(树高h的数量级)】=【O(log2n)】
• 【最坏情况】：
  • 二叉搜索树BST的【每个节点只有一个分支】时
  • 【时间复杂度】：【O(树高h)】=【O(节点数n)】

2）【查找失败ASL】

• 记住ASL计算方式完全按【折半查找树ASL】计算方式，不会回去看笔记
• 【最好情况】：
  • 二叉搜索树BST是【平衡二叉树】时
• 【最坏情况】：
  • 二叉搜索树BST的【每个节点只有一个分支】时

【例题】

二、平衡二叉树（AVL Tree）

1、概念与性质

2、平衡二叉树插入

【小道做法】：

        先不考虑代码等逻辑，完全按人类理解逻辑去 “画画”：每次插入新点后，如果违反打破了平衡性（ |左子树高-右子树高| > 1 ），要怎么“拆散树，再拼接起来？”

• 1、【找不平衡点】
  • 首先，从【插入点】往上找到【第一个平衡因子不是-1、0、1的点（即 |平衡因子| > 1）】，也就是【第一个不平衡点】
• 2、【确定最小平衡子树】
  • 以【该不平衡点】为子树根节点，从【它往下到插入点的路径】算是一个【最小不平衡子树】
• 3、【调整最小平衡树】
  • 从该【不平衡根节点】出发的路径上的【3个顶点（包括根节点）】作为一个子树部分，先调整这3个点
    • 3个点的子树形状有4种排列方式
    • 但不管是哪一种，最终都【只能】变成下面这种【平衡子树形状】
  • 然后剩下的点按【BST二叉搜索树性质】放置（小左大右）
• 以后每次插入新点都依次按照刚刚的逻辑改变：【找不平衡点】、【确定最小平衡子树】、【往下找3个点作为一个子树部分】、【调成3个点的平衡子树】、【下面剩余部分按BST性质放置】.......
  • ​​​​​​​【例子】：依次插入【7、3、15、10、9、8】，并【保持平衡二叉树性质】

；

；

【官方做法（看完就忘，狗都不用）】

• 1、首先要把【最小不平衡树】按下面4类分类
• 2、如果是【LL型最小不平衡树】
  • ​​​​​​​就一步：把【最小不平衡点】为根节点的【3个点的平衡二叉树】往右拉拽
  • 其他点按BST性质插入就行
  • 因此记住：【LL只会导致1次旋转：右旋转】
• 3、如果是【RR型最小不平衡树】
  • ​​​​​​​就一步：把【最小不平衡点】为根节点的【3个点的平衡二叉树】往左拉拽
  • 其他点按BST性质插入就行
  • 因此记住：【RR只会导致1次旋转：左旋转】
• 3、如果是【LR型最小不平衡树】
  • ​​​​​​​注意：会【分2次旋转！！！】：
    • 1）把【最小不平衡点 到 插入点 路径】的【3个点的子树部分】拉成【从上往下降序】
      • 其他点按BST性质插入就行
    • 2）跟【LL】一样，把【最小不平衡点】为根节点的【3个点的平衡二叉树】往右拉拽
      • 其他点按BST性质插入就行
    • 因此记住：【LR会导致两次旋转：先左旋、再右旋】
• 4、如果是【RL型最小不平衡树】
  • ​​​​​​​​​​​​​​注意：会【分2次旋转！！！】：
    • 1）把【最小不平衡点 到 插入点 路径】的【3个点的子树部分】拉成【从上往下降序】
      • 其他点按BST性质插入就行
    • 2）跟【LL】一样，把【最小不平衡点】为根节点的【3个点的平衡二叉树】往右拉拽
      • 其他点按BST性质插入就行
    • 因此记住：【RL会导致两次旋转：先右旋、再左旋】

3、平衡二叉树删除

• 1、首先，删除的最基本操作依旧根据【BST删除】的性质来
• 2、但是如果上面操作导致【破坏了平衡二叉树性质】，则还是要【调整最小平衡树】
  • 但是这里需要注意，逻辑上
    • 还是跟平衡二叉树插入时【调整最小平衡树】一模一样
  • 但是区别是：
    • 由于【调整最小平衡树】需要基于【插入点】来判断，而删除顶点不知道插入点是哪一个
    • 但是我们可以根据【最小平衡点】下面，任意选定【可能的插入点】，分别设计【调整最小平衡树】方案
      • 任意一个插入点对应的【调整最小平衡树】方案都正确！！！
      • 所以【删除后的调整最小平衡树】形状不唯一！！！
      • 【例子】：对下图删除节点【5】，并调整【最小平衡二叉树】

4、拓展总结

【插入时会不会导致树的重新分裂组合】

【逐点插入法】

【各个算法时间复杂度】

【例题】

【特别专题：N个节点的 “XX二叉树” 有几种形状】

• 1）卡特兰树计算公式

  • 但不适用于【平衡二叉树】，因为其有严格限制【 |左子树高 - 右子树高| <= 1 】

• 2）动态规划法：重要，复试机试代码也要用到

  • 先从假设【节点数为0】形状有几种可能：【结果设为F(0)=1】
  • 再假设【节点数为1】形状有几种可能：【结果设为F(0)=1】
  • 再假设【节点数为2】形状有几种可能：【结果设为F(2)】
    • 其中F(2)开始要假设：根节点下有左右两棵子树
    • 总结点数N=2，左右子树共N-1=1个节点（不包括根节点）
    • 则只有2种树形情况【左子树1节点，无右子树】、【右子树1节点，无左子树】
  • 再假设【节点数为3】形状有几种可能：【结果设为F(3)】
    • 其中F(3)开始要假设：根节点下有左右两棵子树
    • 总结点数N=3，左右子树共N-1=2个节点（不包括根节点）
    • 则只有2种节点数情况【左、右子树：0、2】、【左、右子树：2、0】、【左、右子树：1、1】
      • 其中【节点数2】的子树又包含了【F(2)种树形可能】
      • 实际树形是：【F(3)】=【F(0)×F(2)】+【F(2)×F(0)】+【F(1)×F(1)】=【5】
  • 往后一直依此类推，每一种【左右子树节点数情况】都要根据左右子树节点数，得出该情况的树形状是【F(左节点数)×F(右节点数)】
    • 最后把【所有情况的树形状数】相加
• 3）【n个节点数的平衡二叉树的最大深度】
• 4）【h层的平衡二叉树至少几个节点】

【平衡二叉树 VS 二叉排序树】