数据结构之树（4）

摘要：本篇主要讲哈夫曼树、并查集、二叉排序树、平衡二叉树等，非常非常非常重要！！！

一、哈夫曼树

基于霍夫曼树，利用霍夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

在含n个带权叶节点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树

1）每个初始结点最终都会称为叶结点，且权值越小的结点到根结点的路径长度越大

2）哈夫曼树的结点总数2n-1

3）哈夫曼树中不存在度为1的结点

4）哈夫曼树并不唯一，但WPL必然相同且为最优

哈夫曼编码

可变长度编码：允许对不同字符用不等长的二进制位表示

前缀编码：没有一个编码是另一个编码的前缀

用哈夫曼树得到的哈夫曼编码——字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值

取两个最小结点形成一棵树->新数的根和剩下结点中最小结点结合形成新树->以此类推，形成树

给树的分支进行0和1的编码，树的叶子结点为具体内容，由根遍历到叶子结点的编码为值的编码序列。

定义结点

struct TreeNode {
    int data;
    TreeNode* lchild, * rchild, * parent;
    TreeNode(int val) : data(val), lchild(nullptr), rchild(nullptr), parent(nullptr) {}
};

定义最小堆的比较函数

struct Compare {
    bool operator()(TreeNode* l, TreeNode* r) {
        return l->data > r->data; // 最小堆
    }
};

从优先队列中获取最小值

TreeNode* getMin(priority_queue<TreeNode*, vector<TreeNode*>, Compare>& minHeap) {
    if (minHeap.empty()) return nullptr;
    TreeNode* node = minHeap.top();
    minHeap.pop();
    return node;
}

构建哈夫曼树

TreeNode* CreateTree(vector<int>& d) {
    priority_queue<TreeNode*, vector<TreeNode*>, Compare> minHeap;

    // 初始化节点并构建最小堆
    for (int i = 0; i < d.size(); ++i) {
        minHeap.push(new TreeNode(d[i]));
    }

    while (minHeap.size() > 1) {
        TreeNode* left = getMin(minHeap);
        TreeNode* right = getMin(minHeap);

        TreeNode* sum = new TreeNode(left->data + right->data);
        sum->lchild = left;
        sum->rchild = right;
        left->parent = sum;
        right->parent = sum;

        minHeap.push(sum);
    }

    return minHeap.empty() ? nullptr : minHeap.top();
}

二、并查集

逻辑结构——“集合”

用一个数组s[ ]表示“集合”关系（“双亲”）

int UFSets[SIZE];//集合元素数组
//初始化并查集
void Initial(int S[]){
    for(int i=0;i<SIZE;i++）
    S[i]=-1;
}

查：找x所属集合，返回x所属根节点（最坏时间复杂度O(n))

int Find(int S[],int x){
    while(S[x]>=0)//循环寻找x的根
    x=S[x];
    return x;//根的S[ ]小于0
}

拓展：Find操作的优化（压缩路径）

先找到根结点，再将查找路径上所有的结点都挂在根节点下，这样下次找就只需走一次

int Find(int S[ ],int x){

    int root=x;

    while(S[root]>=0)root=S[root];//循环找到根

    while(x!=root){//压缩路径

        int t=S[x];//t指向x的父结点

        S[x]=root;//x直接挂到根节点下

        x=t;
    
     }

    return root;

}

最坏时间复杂度：

Find操作=最坏树高= $O(\alpha(n))$

将n个独立元素通过多次Union合并成一个集合 $O(n\alpha(n))$

并(时间复杂度：O（1）

void Union(int S[ ],int Root1, int Root2){

    if(Root1==Root2)return;

    s[Root2]=Root1;//将根Root2连接到另一根Root1下面

}

Union 操作优化

1、用根节点的绝对值表示树的结点总数

2、Union 操作，让小树合并到大树

void Union(int S[ ],int Root1,int Root2){

    if(Root1==Root2) return;

    if(S[Root2]<S[Root1]){

        S[Root1]+=S[Root2];

        S[Root2]=Root1;//小树合并到大树

    }else{

        S[Root2]+=S[Root1];

        S[Root1]=Root2;

}}

树高不超过[log2 n]+1，提高查找效率

最坏时间复杂度：

Find操作=最坏树高= $O(log_2 n)$

将n个独立元素通过多次Union合并成一个集合 $O(nlog_2 n)$

三、搜索结构之二叉排序树（BST)

可用于元素的有序组织、搜索，又称二叉查找树

左子树上所有结点的关键字均小于根结点的关键字

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

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

-> 左子树节点值<根结点值<右子树

-> 进行中序遍历，可以得到一个递增的有序序列

1、查找

非递归

BSTNode *BST_Search(BSTree T,int key){
    while(T!=NULL&&key!=T->key){//若树空或等于结点值，则结束循环
     if(key<T->key)  T=Y->lchild;  //小于，则在左子树上查找
      else T=T->rchild;//大于，则在右子树上查找
    }
    return T;
}

最坏空间复杂度O(1)

递归

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);//在右子树找

}

最坏空间复杂度O(h)

最好情况

n个结点的二叉树最小高度为[log2 n]+1

平均查找长度=O(log 2 n)

最坏情况

每个结点只有一个分支，树高h=结点数n

平均查找长度=O(n)

2、插入

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)//插入到T的左子树

        return BST_Insert(T->lchild,k);

    else

        return BST_Insert(T->rchild,k);

}

3、构造

void Creat_BST(BSTree &T,int str[),int n)

{    T=NULL;//初始化T为空树

    int i=0;

    while(i<n){//依次将每个关键字插入到二叉排序树

        BST_Insert(T,str[i]);

        i++;

        }

}

4、删除

1）若被删除结点z时叶结点，则直接删除，不会破坏二叉排序树的性质

2）若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，代替z的位置

3）结点z有左、右两棵子树，则令z的直接后继（或直接前驱）替代z,然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转化成第一或第二种情况。

可用其后继结点顶替，再删除后继结点

或用其前驱结点顶替，再删除前驱结点

前驱:左子树最右下的结点

后继：右子树中最左下的结点

四、搜索结构之平衡二叉树（AVL)

树上任一结点的左子树和右子树的高度只差不超过1

//平衡二叉树结点

typedef struct AVLNode{

    int key;//数据域

    int balance;//平衡因子

    struct AVLNode *lchild,*rchild;

}AVLNode,*AVLTree;

1、插入

从插入点往回找到第一个不平衡结点，调整以该结点为根的子树

每次调整的对象都是“最小不平衡子树”

调整最小不平衡子树A

由于在结点A的左孩子（L）的左子树（L）上插入了新节点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。

将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树

（直接画图就明白了）

RR-在A的右孩子的右子树中插入导致不平衡（左单旋转）

由于在结点A的右孩子（R）的右子树（R）上插入了新节点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。

将A的右孩子B向左上旋转代替A成为根节点，将A结点向下旋转成为B的左子树的根节点，而B的原左子树成为A结点的右子树

LR-在A的左孩子的右子树中插入导致不平衡(先左后右双旋转)

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

查找效率

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

平衡二叉树——树上任一结点的左子树和右子树的高度之差不超过1

假设以nh表示深度为h的平衡树中含有的最少结点数

则有n0=0,n1=1,n2=2, $n_h=n_{ h-1} +n_{ h-2 }+1$

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

2、删除

具体步骤

1、删除结点（方法同“二叉排序树”）

2、一路向北找到最小不平衡子树

3、找最小不平衡子树下，“个头”最高的儿子，孙子

4、根据孙子的位置，调整平衡（LL,RR,LR,RL)

5、如果不平衡向上传导，继续2

O(log 2 n)

五、搜索结构之红黑树

为什么发明红黑树

平衡二叉树AVL：插入/删除很容易破坏“平衡”特性，需要频繁调整数的形态。如：插入操作导致不平衡，则需要先计算平衡因子，找到最小不平衡子树（时间开销大），再进项LL,RR,LR,RL调整

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

AVL：适用于以查为主，很少插入/删除

RBT:适用于频繁插入、删除的场景，实用性更强

1、每个结点或是红色，或是黑色的

2、根结点是黑色

3、叶结点（外部结点，NULL结点，失败结点）均是黑色的

4、不存在两个相邻的红结点（即红结点的父结点和孩子结点均是黑色）

5、对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数目相同

性质

1、从根结点到叶结点的最长路径不大于最短路径的2倍（对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数目相同，结点间又穿插红结点）

2、有n个内部结点的红黑树高度h<=2log2(n+1)

3、查找O(log 2 n)

六、搜索结构之B树

1、概念

2、插入删除

7.4_2_B树的插入删除_哔哩哔哩_bilibili

3、B+树

七、排序之败者树

利用败者树优化多路平衡归并问题

选出最小

下一轮选取，就可以在原来的败者树基础上进行比较，每一层仅需比较一次