首页 计算机科学 数据结构

# 二叉排序树

二叉排序树，又称二叉查找树 (BST)，一颗二叉树或者是空二叉树，或者具有如下性质的二叉树：

左子树上所有结点的关键字均小于根节点的关键字（左子树结点值 <根结点值 < 右子树结点值 -> 进行中序遍历，可以得到一个递增的有序序列）

右子树上所有结点的关键字均大于根节点的关键字

左子树和右子树又各是一棵二叉排序树。

//二叉排序树的节点
typedef struct BSTNode{
    int key;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

# 查找

若树非空，目标值与根节点的值比较：若相等，则查找成功；若小于根节点，则在左子树上查找，否则在右子树上查找。

查找成功，返回结点指针；查找失败返回 NULL

//在二叉排序树中查找为key的结点
BSTNode *BST_Search(BSTree T,int key){
    while(T!=NULL && key!=T->key){   //若树空或等于根结点，则结束循环
        if(key<T->key)    //小于，则在左子树查找
            T=T->lchild;
        else  //大于，则在右子树上查找
            T=T->rchild;
    }
    return T;
}
//在二叉排序树中查找值为key的节点(递归实现)
BSTNode *BSTSearch(BSTree T,int key){
    if(T==NULL)
        return NULL;  //查找失败
    if(key==T->key)
        return T; //查找成功
    else if(key<T->key)
        return BSTSearch(T->lchild,key);  //在左子树中找
    else
        return BSTSearch(T->rchild,key);  //在右子树中找
}

# 插入

若原二叉树为空，则直接插入结点；否则，若关键字 k 小于根节点值，则插入到左子树，若关键字 k 大于根结点值，则插入到右子树

//在二叉排序树插入关键字为k的新节点(递归实现)
int BST_Insert(BSTree &T,int k){
    if(T==NULL){     //原数为空，新插入的结点为根结点
        T=(BSTree)malloc(sizeof(BSTNode));
        T->key=k;
        T->lchild=T->rchild=NULL;
        return 1;   //返回1，插入成功
    }
    else if(k==T->key)  //树中存在相同关键字的节点，插入失败
        return 0;
    else if(k<T->key)
        return BST_Insert(T->lchild,k);
    else
        return BST_Insert(T->rchild,k);
}

# 构造

//按照str[]中的关键字序列建立二叉排序树
void Creat_BST(BSTree &T,int str[],int n){
    T=NULL;    //初始时，T为空
    int i=0;
    while(i<n){  //依次将每个关键字插入到二叉排序树中
        BST_insert(T,str[i]);
        i++;
    }
}

# 删除

先搜索到目标结点：

  • 若被删除的结点 z 是叶节点，则直接删除，不会破坏二叉排序树的性质
  • 若结点 z 只有一颗左子树或右子树，则让 z 的子树称为 z 父节点的子树，替代 z 的位置
  • 若结点 z 由左、右两棵子树，则令 z 的直接后继 (或直接前驱) 替代 z，然后从二叉排序树中删去这个直接后继 (或直接前驱)，这样就转换成了第一或第二种情况

# 查找效率分析

若树高 h，找到最下层的一个结点需要对比 h 次

最好情况：n 个结点的二叉树最小高度为⌊log2n⌋+1\lfloor log_2n\rfloor+1，平均查找长度为O(log2n)O(log_2n)

最坏情况：每个节点只有一个分支，树高 h = 节点数 n，平均查找长度 = O (n)

# 平衡二叉树

平衡二叉树，简称平衡树 (AVL 树)—— 树上任一节点的左子树和右子的树的深度之差不超过 1

结点的平衡因子 = 左子树高 - 右子树高，平衡二叉树结点的平衡因子的值只可能是 - 1,0,1

只要有任一结点的平衡因子绝对值大于 1，就不是平衡二叉树

//平衡二叉树结点
typedef struct AVLNode{
    int key;   //数据域
    int balance; //平衡因子
    struct AVLNode *lchild,*rchild;
}AVLNode,*AVLTree;

# 插入

查找路径上的所有结点都有可能受到影响

从插入点往回找到第一个不平衡结点，调整以该结点为根的子树，每次调整对象都是 "最小不平衡子树"

在插入操作中，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡

# 调整最小不平衡子树

# LL：在 A 的左孩子的左子树插入导致不平衡

右单旋转：（假设最小不平衡子树的根结点为 A，左孩子为 B）

由于结点 A 的左孩子 (L) 的左子树 (L) 上插入了新结点，A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要一次向右的旋转操作。将 A 的左孩子 B 向右上旋转代替 A 称为根结点，将 A 结点向右下旋转称为 B 的右子树的根节点，而 B 的原右子树作为 A 结点的左子树

# RR：在 A 的右孩子的右子树插入导致不平衡

左单旋转：（假设最小不平衡子树的根结点为 A，右孩子为 B）

由于结点 A 的右孩子 (R) 的右子树 (R) 上插入了新结点，A 的平衡因子由 - 1 减至 - 2，导致以 A 为根的子树失去平衡，需要一次向左的旋转操作。将 A 的右孩子 B 向左上旋转代替 A 称为根结点，将 A 结点向左下旋转称为 B 的左子树的根节点，而 B 的原左子树作为 A 结点的右子树

右旋：实现 f 向右下旋转，p 向右上旋转：其中 f 是父亲，p 为左孩子，gf 为 f 的父亲

f->lchild=p->rchild;
p->rchild=f;
gf->lchild/rchild=p;

左旋：实现 f 向左下旋转，p 向左上旋转：其中 f 是父亲，p 为左孩子，gf 为 f 的父亲

f->rchild=p->lchild;
p->lchild=f;
gf->lchild/rchild=p;
# LR：在 A 的左孩子的右子树插入导致不平衡

先左后右双旋转：(假设最小不平衡子树的根结点为 A，左孩子为 B，左孩子的右孩子为 C)

由于结点 A 的左孩子 (L) 的右子树 (R) 上插入了新结点，A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将 A 结点的左孩子 B 的右子树的根结点 C 向左上旋转提升至 B 结点的位置，然后再把该 C 结点向右上旋转提升到 A 结点的位置

注：左旋和右旋与上方一样

# RL：在 A 的右孩子的左子树插入导致不平衡

先右后左双旋转：(假设最小不平衡子树的根结点为 A，右孩子为 B，右孩子的左孩子为 C)

由于结点 A 的右孩子 (R) 的左子树 (L) 上插入了新结点，A 的平衡因子由 - 1 减至 - 2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将 A 结点的右孩子 B 的左子树的根结点 C 向右上旋转提升至 B 结点的位置，然后再把该 C 结点向左上旋转提升到 A 结点的位置

注：左旋和右旋与上方一样

# 查找效率分析

若树高为 h，则最坏情况下，查找一个关键字最多需要对比 h 次，即查找操作的时间复杂度不可能超过 O (h)

假设以nhn_h 表示深度为 h 的平衡二叉树中含有最少的结点数。则有n0=1,n1=1,n2=2n_0=1,n_1=1,n_2=2，并且有nh=nh−1+nh−2+1n_h=n_{h-1}+n_{h-2}+1

可以证明含有 n 个结点的平衡二叉树的最大深度为O(log2n)O(log_2n)，平衡二叉树的平均查找长度为O(log2n)O(log_2n)

# 删除

平衡二叉树的删除操作：

  • 删除结点后，要保持二叉排序树的特性不变 (左 < 中 < 右)
  • 若删除结点导致不平衡，则需要调整平衡

平衡二叉树的删除操作具体步骤：

  • 删除结点 (方法同二叉排序树)
    • 若删除的结点是叶子结点，直接删
    • 若删除的结点有一个子树，用子树顶替删除位置
    • 若删除的结点有两棵子树，用前驱 (或后继) 结点顶替，并转换为对前驱 (或后继) 结点的删除
  • 一路向上找到最小不平衡子树
  • 找到最小不平衡子树下，高度最高的儿子和孙子
  • 根据孙子的位置，调整平衡 (LL/RR/LR/RL)
    • 孙子在 LL：儿子右单旋
    • 孙子在 RR：儿子左单旋
    • 孙子在 LR：孙子先左旋，再右旋
    • 孙子在 RL：孙子先右旋，再左旋
  • 如果不平衡向上传导，则继续第二步
    • 对最小不平衡子树的旋转可能导致树变矮，从而导致上层祖先不平衡 (不平衡的向上传递)

平衡二叉树删除操作时间复杂度 =O(log2n)O(log_2n)

# 红黑树

平衡二叉树 AVL：插入 / 删除很容易破坏 "平衡" 特性，需要频繁调整树的形态

红黑树 RBT：插入 / 删除很多时候不会破坏 "红黑" 特性，无需频繁调整树的形态。即使需要调整，一般可以在常数级时间内完成

平衡二叉树：以查为主、很少插入 / 删除的场景

红黑树：适用于频繁插入、删除的场景，实用性更强

红黑树是二叉排序树 —— 左子树结点值 < 根结点值 < 右子树结点值

  • 每个结点或是红色，或是黑色的
  • 根节点是黑色的
  • 叶结点 (外部结点、NULL 结点、失败结点) 均是黑色的
  • 不存在两个相邻的红结点 (即红结点的父节点和孩子结点均是黑色的)
  • 对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数目相同
struct RBNode {      //红黑树结点定义
    int key;         //关键字的值
    RBNode* parent;  //父节点指针
    RBNode* lchild;  //左孩子指针
    RBNode* rchild;  //右孩子指针
    int color;       //结点颜色，如：可用0/1表示黑/红
}

结点的黑高 bh—— 从某结点出发 (不含该结点) 到达任一空叶结点的路径上黑结点总数

性质：

  • 从根结点到叶结点的最长路径不大于最短路径的 2 倍
  • 有 n 个内部结点的红黑树高度h≤2log2(n+1)h\le2log_2(n+1)
    • 红黑树查找操作时间复杂度 =O(log2n)O(log_2n)

查找

与 BST、AVL 相同，从根出发，左小右大，若查找到一个空叶结点，则查找失败

# 插入

  • 先查找，确定插入位置 (原理同二叉排序树)，插入新结点
  • 新结点是根 —— 染为黑色
  • 新结点非根 —— 染为红色
    • 若插入新结点后依然满足红黑树定义，则插入结束
    • 若插入新结点后不满足红黑树定义，需要调整，使其重新满足红黑树定义
      • 如何调整：看新结点叔叔的颜色
      • 若叔叔为黑色：旋转 + 染色
        • LL 型：右单旋，父换爷 + 染色
        • RR 型：左单旋，父换爷 + 染色
        • LR 型：左、右双旋，儿换爷 + 染色
        • RL 型：右、左双旋，儿换爷 + 染色
      • 若叔叔为红色：染色 + 变新
        • 叔父爷染色，爷变为新结点

结点的黑高 bh—— 从某结点出发 (不含该结点) 到达任一叶结点的路径上黑结点总数

若根结点黑高为 h，内部结点数 (关键字) 最少有2h−12^h-1 个

# 删除

红黑树删除操作的时间复杂度 =O(log2n)O(log_2n)

在红黑树中删除结点的处理方式和二叉排序树的删除一样

按第二步删除结点后，可能破坏红黑树特性，此时需要调整结点颜色、位置，使其再次满足红黑树特性