当前位置： 首页 > ds >正文

二叉排序树（BST），平衡二叉树（AVL）

ds 2025/5/14 5:39:07

二叉排序树(BST)

基本概念

  • 也叫二叉查找树，二叉搜索树(BST:Binary Search Tree)
  • 在二叉树的基础上加一个约束——顺序性：左子树<根节点<右子树(以递增为例，递减也可以，有顺序性就OK)

性质：

  1. 若左子树为空，则根节点小于右子树中所有节点
  2. 若右子树为空，则根节点大于左子树中所有节点
  3. 其左右子树也为二叉排序树

用途：

  1. 在 l o g 2 ( n + 1 ) log_{2}(n+1) log2​(n+1)的次数内找到目标数据，比直接遍历节省时间。

基本操作

增加

  1. 二叉链表存树
  2. 若为空树，直接创建节点
  3. 若非空树，遍历找到要插入的字节点，使用pre记录父亲节点
非递归版
//插入
BSTree insert(BSTree r, int x)
{BSTNode* p = r;BSTNode* pre = NULL;//查找需要插入的位置while (p != NULL) {if (x < p->data) {pre = p;p = p->l;}else {pre = p;p = p->r;}}BSTNode* s = (BSTNode*)malloc(sizeof(BSTNode));s->data = x;s->l = s->r = NULL;if (s->data < pre->data) {pre->l = s;}else {pre->r = s;}return r;
}
递归版
  1. 递归出口：当碰到NULL时，即为需要插入的地方。
BSTree insert_D(BSTree r, int x)
{if (r == NULL){BSTNode* s = (BSTNode*)malloc(sizeof(BSTNode));s->data = x;s->l = s->r = NULL;return s;}if (x < r->data){r->l = insert_D(r->l, x);return r;}if (x > r->data){r->r = insert_D(r->r, x);return r;}
}

删除

  1. 递归找到删除节点
  2. 节点的度为0，直接删除，让父节点指针指向为空。
  3. 节点的度为1，直接让字孩子顶替，
  4. 节点的度为2，将中序遍历前驱或者后继节点顶替该节点，
//删除
BSTree BSTdelete(BSTree root, int x)
{if (root == NULL) {return NULL;}if (x > root->data) {root->r = BSTdelete(root->r, x);}else if (x < root->data) {root->l = BSTdelete(root->l, x);}else {if (root->l != NULL && root->r != NULL) {//度为2//用前驱节点替换BSTNode* p = root->l;while (p->r != NULL) {p = p->r;}root->data = p->data;root->l = BSTdelete(root->l, p->data);}else {BSTNode* p = root;if (root->l == NULL) {root = root->r;}else {root = root->l;}free(p);p = NULL;}}return root;
}

查找

  1. 遍历寻找，小了去左子树找，大了去右子树找。
非递归版
void search(BSTree root, int x)
{BSTNode* p = root;while (p != NULL && p->data != x) {if (x < p->data) {p = p->l;}else {p = p->r;}}if (p == NULL){printf("未找到\n");}else {printf("已找到\n");}
}
递归版
void search_D(BSTree root, int x)
{if (root == NULL){printf("未找到\n");}if (root->data == x){printf("已找到\n");}if (x < root->data){search_D(root->l, x);}if (x > root->data){search_D(root->r, x);}
}

完整代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>typedef struct BSTnode {int data;struct BSTnode* l;struct BSTnode* r;
}BSTNode,*BSTree;BSTree initBST(int x)
{BSTNode* r = (BSTNode*)malloc(sizeof(BSTNode));if (r == NULL) {printf("内存分配成功\n");return;}r->data = x;r->l = r->r = NULL;return r;
}//插入
BSTree insert(BSTree r, int x)
{BSTNode* p = r;BSTNode* pre = NULL;while (p != NULL) {if (x < p->data) {pre = p;p = p->l;}else {pre = p;p = p->r;}}BSTNode* s = (BSTNode*)malloc(sizeof(BSTNode));s->data = x;s->l = s->r = NULL;if (s->data < pre->data) {pre->l = s;}else {pre->r = s;}return r;
}BSTree insert_D(BSTree root, int x)
{if (root == NULL){BSTNode* s = (BSTNode*)malloc(sizeof(BSTNode));s->data = x;s->l = s->r = NULL;return s;}if (x < root->data){root->l = insert_D(root->l, x);return root;}if (x > root->data){root->r = insert_D(root->r, x);return root;}
}//查找
void search(BSTree root, int x)
{BSTNode* p = root;while (p != NULL && p->data != x) {if (x < p->data) {p = p->l;}else {p = p->r;}}if (p == NULL){printf("未找到\n");}else {printf("已找到\n");}
}void search_D(BSTree root, int x)
{if (root == NULL){printf("未找到\n");}if (root->data == x){printf("已找到\n");}if (x < root->data){search_D(root->l, x);}if (x > root->data){search_D(root->r, x);}
}//输出
void inOrder(BSTree root)
{if (root == NULL) {return;}if (root->l != NULL){inOrder(root->l);}printf("%d ", root->data);if (root->r != NULL){inOrder(root->r); }
}//删除
BSTree BSTdelete(BSTree root, int x)
{if (root == NULL) {return NULL;}if (x > root->data) {root->r = BSTdelete(root->r, x);}else if (x < root->data) {root->l = BSTdelete(root->l, x);}else {if (root->l != NULL && root->r != NULL) {//度为2//用前驱节点替换BSTNode* p = root->l;while (p->r != NULL) {p = p->r;}root->data = p->data;root->l = BSTdelete(root->l, p->data);}else {BSTNode* p = root;if (root->l == NULL) {root = root->r;}else {root = root->l;}free(p);p = NULL;}}return root;
}int main()
{int n;int a[100];scanf_s("%d", &n);for (int i = 1; i <= n; i++) {scanf_s("%d", &a[i]);}BSTree root = initBST(a[1]);if (root == NULL) {printf("建树失败\n");return 0;}for (int i = 2; i <= n; i++){insert_D(root, a[i]);}inOrder(root);printf("\n");BSTdelete(root, 6);inOrder(root);return 0;
}
/*
9
8 3 10 1 6 14 4 7 13
*/

应用场景

  • 可以将查找操作的次数降到 l o g ( n ) log(n) log(n)
  • 当原序列有序时，构建的BST是斜树，没有降低操作次数
  • 优化：使二叉树左右子树的高度差不多，看上去比较饱满，像完全二叉树，此时可以在二叉排序树上加上一个平衡因子，又称为二叉平衡树(AVL)

二叉平衡树(AVL)

精美图形化演示如何旋转：【平衡二叉树(AVL树)】
AVL的插入和删除操作图形化展示：【「六分钟速通」平衡二叉树(AVL树)的插入与删除】

基本概念

  1. 一个节点平衡因子：该节点左右子树的高度差<=1
  2. AVL树：
    1. 可以是空树
    2. 若非空，保持顺序性并且任何一个节点的左右子树高度差的绝对值不超过
    3. 任何一个节点的左右子树也都是AVL树
  3. AVL的核心精髓就在于旋转之中，弄清楚了旋转，如何插入和删除也是顺水推舟的事情了

基本操作

插入

  1. 先按BST的插入方式操作cur
  2. 判断cur节点是否失衡，没有失衡，over
  3. 若失衡，优先调整以x最近的长辈为孩子的失衡子树–最小失衡子树

如何调整：

  • 失衡的四种情况：

    1. L L 失衡节点z的左孩子y的左子树中插入节点x导致失衡。
      p=x->left
      x->left=p->right
      p->right=x

    2. L R 失衡节点z的左孩子的右子树中插入节点导致失衡
      先以y为根左旋，转化为LL的情况

    3. R R 失衡节点z的右孩子的右子树中插入节点导致失衡
      p=p->right
      x->right=p->left
      p->left=x;

    4. R L 失衡节点z的右孩子的左子树中插入节点导致失衡
      先以y为根右旋，转化为RR

  • 调整操作：
    • 旋转操作，使得孩子节点变为根节点，将父节点旋转为孩子的孩子。
//LL失衡
AVLTree LL_rotation(AVLTree x)
{AVLnode* y = x->l;x->l = y->r;y->r = x;x->high = max(get_h(x->l), get_h(x->r)) + 1;y->high = max(get_h(y->l), get_h(y->r)) + 1;return y;
}//RR失衡
AVLTree RR_rotation(AVLTree x)
{AVLnode* y = x->r;x->r = y->l;y->l = x;x->high = max(get_h(x->l), get_h(x->r)) + 1;y->high = max(get_h(y->l), get_h(y->r)) + 1;return y;
}//LR失衡
AVLTree LR_rotation(AVLTree x)
{x->l = RR_rotation(x->l);x = LL_rotation(x);return x;
}//RL失衡
AVLTree RL_rotation(AVLTree x)
{x->r = LL_rotation(x->r);x = RR_rotation(x);return x;
}

查找操作

  • 与二叉排序树的查找完全一致。

删除

  • 删除可能导致失衡，但只会影响到与该节点有联系的父节点
//删除
AVLTree delete_AVL(AVLTree root, int k)
{if (root == NULL){return root;}if (k < root->data){root->l = delete_AVL(root->l, k);//root可能失衡if (get_h(root->r) - get_h(root->r) > 1){AVLnode* temp = root->r;if (get_h(temp->r) >= get_h(temp->l))//RR{root = RR_rotation(root);}else {//RLroot = RL_rotation(root);}}}else if (k > root->data){root->r = delete_AVL(root->r, k);//root可能失衡if (get_h(root->l) - get_h(root->r) > 1){AVLnode* temp = root->l;if (get_h(temp->l) >= get_h(temp->r))//LL{root = LL_rotation(root);}else {//LRroot = LR_rotation(root);}}}else if (root->l != NULL && root->r != NULL)//度为2的节点{AVLnode* re = find_re(root->r);root->data = re->data;root->r = delete_AVL(root->r, re->data);//root可能失衡if (get_h(root->l) - get_h(root->r) > 1){AVLnode* temp = root->l;if (get_h(temp->l) >= get_h(temp->r))//LL{root = LL_rotation(root);}else {//LRroot = LR_rotation(root);}}}else {//度为1或0的节点AVLnode* c = root;if (root->l == NULL){root = root->r;}else {root = root->l;}free(c);c = NULL;}if(root!=NULL)	root->high = max(get_h(root->l), get_h(root->r)) + 1;return root;
}

完整代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>//AVL节点结构
typedef struct AVLnode
{int data;struct AVLnode* l;struct AVLnode* r;int high;//节点的高度
}AVLnode,*AVLTree;//初始化
AVLTree initAVLTree(int k)
{AVLnode* root = (AVLnode*)malloc(sizeof(AVLnode));root->data = k;root->l = root->r = NULL;root->high = 1;return root;
}//得到节点高度
int get_h(AVLnode* x)
{if (x != NULL){return x->high;}else {return 0;}
}//LL失衡
AVLTree LL_rotation(AVLTree x)
{AVLnode* y = x->l;x->l = y->r;y->r = x;x->high = max(get_h(x->l), get_h(x->r)) + 1;y->high = max(get_h(y->l), get_h(y->r)) + 1;return y;
}//RR失衡
AVLTree RR_rotation(AVLTree x)
{AVLnode* y = x->r;x->r = y->l;y->l = x;x->high = max(get_h(x->l), get_h(x->r)) + 1;y->high = max(get_h(y->l), get_h(y->r)) + 1;return y;
}//LR失衡
AVLTree LR_rotation(AVLTree x)
{x->l = RR_rotation(x->l);x = LL_rotation(x);return x;
}//RL失衡
AVLTree RL_rotation(AVLTree x)
{x->r = LL_rotation(x->r);x = RR_rotation(x);return x;
}//插入
AVLTree insert_AVL(AVLTree root, int k)
{if (root == NULL){AVLnode* s = (AVLnode*)malloc(sizeof(AVLnode));s->data = k;s->l = s->r = NULL;s->high = 1;return s;}if (k < root->data){root->l = insert_AVL(root->l, k);//判断是否失衡if (get_h(root->l) - get_h(root->r) > 1){AVLnode* l = root->l;//判断失衡情况if (k < l->data){root = LL_rotation(root);}else {root = LR_rotation(root);}}}if (k > root->data){root->r = insert_AVL(root->r, k);//判断是否失衡if (get_h(root->r) - get_h(root->l) > 1){AVLnode* r = root->r;//判断失衡情况if (k > r->data){root = RR_rotation(root);}else {root = RL_rotation(root);}}}root->high = max(get_h(root->l), get_h(root->r)) + 1;return root;
}//中序遍历
void inOrder(AVLTree root)
{if (root != NULL){inOrder(root->l);printf("%d %d\n", root->data, root->high);inOrder(root->r);}
}//找后继
AVLnode* find_re(AVLnode* p)
{while (p->l != NULL){p = p->l;}return p;
}//删除
AVLTree delete_AVL(AVLTree root, int k)
{if (root == NULL){return root;}if (k < root->data){root->l = delete_AVL(root->l, k);//root可能失衡if (get_h(root->r) - get_h(root->r) > 1){AVLnode* temp = root->r;if (get_h(temp->r) >= get_h(temp->l))//RR{root = RR_rotation(root);}else {//RLroot = RL_rotation(root);}}}else if (k > root->data){root->r = delete_AVL(root->r, k);//root可能失衡if (get_h(root->l) - get_h(root->r) > 1){AVLnode* temp = root->l;if (get_h(temp->l) >= get_h(temp->r))//LL{root = LL_rotation(root);}else {//LRroot = LR_rotation(root);}}}else if (root->l != NULL && root->r != NULL)//度为2的节点{AVLnode* re = find_re(root->r);root->data = re->data;root->r = delete_AVL(root->r, re->data);//root可能失衡if (get_h(root->l) - get_h(root->r) > 1){AVLnode* temp = root->l;if (get_h(temp->l) >= get_h(temp->r))//LL{root = LL_rotation(root);}else {//LRroot = LR_rotation(root);}}}else {//度为1或0的节点AVLnode* c = root;if (root->l == NULL){root = root->r;}else {root = root->l;}free(c);c = NULL;}if(root!=NULL)	root->high = max(get_h(root->l), get_h(root->r)) + 1;return root;
}int main()
{int n;int a[105];scanf_s("%d", &n);for (int i = 1; i <= n; i++){scanf_s("%d", &a[i]);}AVLTree root = initAVLTree(a[1]);for (int i = 2; i <= n; i++){root = insert_AVL(root, a[i]);}inOrder(root);int sign;scanf_s("%d", &sign);root = delete_AVL(root, sign);inOrder(root);return 0;
}
/*
8
1 2 3 4 5 6 7 8
*/
http://www.xdnf.cn/news/5916.html

相关文章：

  • 鸿蒙PC版体验_画面超级流畅_具备terminal_无法安装windows、linux软件--纯血鸿蒙HarmonyOS5.0工作笔记017
  • MATLAB Simulink在Autosar和非Autosar工程下的开发流程
  • JVM之虚拟机运行
  • Nacos源码—9.Nacos升级gRPC分析八
  • 微信小程序学习之底部导航栏
  • 初识Linux
  • spark sql基本操作
  • C++STL——map和set的使用
  • Azure 应用的托管身份与服务主体
  • 在scala中使用sparkSQL连接MySQL并添加新数据
  • uniapp-商城-56-后台 新增商品（弹窗属性继续分析）
  • 解构认知边界：论万能方法的本体论批判与方法论重构——基于跨学科视阈的哲学-科学辩证
  • Node.js 中的 URL 模块
  • sql 备份表a数据到表b
  • 论文精读：YOLO-UniOW: Efficient Universal Open-World Object Detection
  • 【Pandas】pandas DataFrame cumprod
  • 一文理清人工智能，机器学习，深度学习的概念
  • TCP协议十大核心特性深度解析：构建可靠传输的基石
  • 标贝科技：大模型领域数据标注的重要性与标注类型分享
  • Python格式化字符串学习笔记
  • 如何使用远程桌面控制电脑
  • 网页禁止粘贴的解决方法（以学习通网页为例）
  • puppy系统详解
  • 中国古代史4
  • Android中ConstraintLayout约束布局使用详解
  • 虚拟主机与独立服务器：哪个更好？
  • MFCC特征提取及Griffin-Lim算法（librosa实现）
  • 使用 AddressSanitizer 检测栈内存越界错误
  • 如何配置本机host文件
  • Power BI 实操案例，将度量值转化为切片器（动态切换分析指标）