数据结构_平衡二叉树

embedded/2024/12/24 10:10:39/

结点类

构造函数分为有参和无参,相同点都是初始化树高为1

class Node
{
public:int data;  // 用于输出int val;   // 数据域,用于排序int height; // 树高Node* left;Node* right;Node();Node(int v, int d);static int max(int a, int b);
};Node::Node()
{data = -1;val = -1;height = 1;left = nullptr;right = nullptr;
}Node::Node(int v, int d)
{data = d;val = v;height = 1;left = nullptr;right = nullptr;
}int Node::max(int a, int b)
{return (a > b) ? a : b;
}

获取平衡因子

左子树树高减去右子树树高

int getB(Node* n)
{int leftHeight = (n->left) ? n->left->height : 0;int rightHeight = (n->right) ? n->right->height : 0;return leftHeight - rightHeight;
}

解决RR型不平衡,左旋

  • 新的根节点为当前根节点的右子树
  • 当前根结点的右子树的左子树,改变后为当前根结点的右子树(如果存在的话)
  • 当前根节点变为新的根节点的左子树
  • 最后要更新改变前后两个新旧根节点的树高,都等于1 + 左右子树的树高比较后的最大值
Node* leftRoatte(Node* n) // 左旋(RR)
{Node* newroot = n->right;Node* T2 = newroot->left;newroot->left = n;n->right = T2;// 更新树高n->height = 1 + Node::max(n->left ? n->left->height : 0, n->right ? n->right->height : 0);newroot->height = 1 + Node::max(newroot->left ? newroot->left->height : 0, newroot->right ? newroot->right->height : 0);return newroot;
}

解决LL型不平衡,右旋

实现方法与RR型大差不差

Node* rightRoatte(Node* n) // 右旋(LL)
{Node* newroot = n->left;Node* T2 = newroot->right;newroot->right = n;n->left = T2;// 更新树高n->height = 1 + Node::max(n->left ? n->left->height : 0, n->right ? n->right->height : 0);newroot->height = 1 + Node::max(newroot->left ? newroot->left->height : 0, newroot->right ? newroot->right->height : 0);return newroot;
}

结点的插入函数

  • 如果传入进来的为空结点,即当前结点无数据,则需要把传入进来的用于排序和输出的值作为参数构造一个新的结点,然后返回出去
  • 否则,则进行判断,判断当前结点的关键值与传入进来的关键值进行判断,如果传入进来的值比当前结点的值要小,则表示需要插入进当前结点的左子树,递归调用插入函数,参数是当前结点的左子树,关键值和数据域,返回后的结点赋值给当前结点的左子树
  • 如果传入进来的关键值大于当前结点的关键值,则插入右子树,方法类似
  • 如果当前结点的关键值等于传入进来的关键值,则表示这个值已经在树中存在,不需要插入,则直接将当前结点的返回出去
  • 执行完插入结点的操作后,需要更新树高,方法一样
  • 还需要更新平衡因子,因为当插入一个结点后,需要判断此时是否为平衡二叉树,根据不同结点的平衡因子进行不同的调整
  • 首先获取当前根结点的平衡因子,如果当前根节点的平衡因子大于1,且当前结点的左子树根结点大于0,即他还有左子树,则为LL型,则调用右旋函数,返回调用后的结果
  • 如果当前根节点的的平衡因子大于1,且当前根节点的左子树的根节点小于0,则其有右子树,为LR型,LR型首先要将当前结点的左子树为参数进行左旋,然后再将当前结点进行右旋,返回调用后的结果
  • 其他两种情况类似
  • 最后返回当前结点
Node* Insert(Node* now, int key, int data)
{if (now == nullptr){return new Node(key, data);}if (key < now->val){now->left = Insert(now->left, key, data);}else if (key > now->val){now->right = Insert(now->right, key, data);}else{return now;  // Key already exists, don't insert duplicate}// 更新树高now->height = 1 + Node::max(now->left ? now->left->height : 0, now->right ? now->right->height : 0);// 获取当前结点的平衡因子int balance = getB(now);if (balance > 1 && getB(now->left) >= 0) // LL{return rightRoatte(now);}else if (balance > 1 && getB(now->left) < 0) // LR{now->left = leftRoatte(now->left);return rightRoatte(now);}else if (balance < -1 && getB(now->right) <= 0) // RR{return leftRoatte(now);}else if (balance < -1 && getB(now->right) > 0) // RL{now->right = rightRoatte(now->right);return leftRoatte(now);}return now;
}

http://www.ppmy.cn/embedded/148307.html

相关文章

小程序租赁系统的优势与未来发展潜力分析

内容概要 小程序租赁系统正在成为租赁行业的热门工具&#xff0c;大家都在谈论它的优势和未来潜力。让我们简单分析一下这些优势&#xff1a; “便捷性和高效性是小程序租赁系统的两个杀手锏&#xff0c;让我们一起揭开它们的神秘面纱&#xff01;” 在许多情况下&#xff0c;…

Elasticsearch相关知识@1

目录标题 Lucene1. **什么是 Lucene?**2. **Lucene 在 Elasticsearch 中的作用**3. **Lucene 的核心功能**(1) **倒排索引**(2) **分词**(3) **查询解析**(4) **相关性评分** 4. **为什么 Elasticsearch 使用 Lucene?**5. **Lucene 和 Elasticsearch 的区别**6. **总结** 分片…

Spring(七)Spring Cloud----Feign、Zuul和Apollo

文章目录 一、服务调用Feign1.1 Feign的基本使用1.2 Feign的属性配置1.2.1 Ribbon配置1.2.2 Hystrix配置 二、网关服务Zuul2.1 Zuul的基本使用2.1.1 请求路由2.1.2 请求过滤 2.2 路由详解2.2.1 传统路由配置2.2.2 服务路由配置2.2.3 服务路由的默认规则2.2.4 自定义路由映射规则…

linux 根据名称 杀死linux 上某个jar进程或其他进程

在 Linux 系统上&#xff0c;可以通过进程名称杀死特定的 .jar 进程。以下是具体的步骤&#xff1a; 1. 查找目标进程 通过 ps 命令查找运行的 .jar 文件对应的进程。 示例&#xff1a; 假设目标进程的 .jar 文件名是 myapp.jar。 ps aux | grep myapp.jar输出示例&#x…

步进电机控制原理

前言 讲讲步进电机的控制原理。相关知识做介绍&#xff0c;以及个人的理解。 基础知识PPT 频率越快速度越快 原理总结 一、什么是步进电机 步进电机是一种将电脉冲信号转换成相应角位移或线位移的电动机。每输入一个脉冲信号&#xff0c;转子就转动一个角度或前进一步&#…

【总结(三)】单片机重点知识总结记录(串口重定向+按键消抖+延时)

一.串口重定向 串口重定向代码如下 注意&#xff1a; 要添加头文件include "stdio.h"要勾选微库&#xff0c;即Use MicroLIB /**********重定向************/ //串口1 int fputc(int ch, FILE *f) {HAL_UART_Transmit(&huart1, (uint8_t *)&ch, 1, 0xffff)…

【JUC编程】JUC 多线程基础全面解析(待更新版)

文章目录 JUC 多线程基础全面解析一、线程与并发基础1. 什么是线程&#xff1f;2. 并发与并行的区别3. Java 线程的基本创建方式 二、JUC 核心组件1. 线程池2. 锁机制3. 并发集合 三、线程间通信工具1. CountDownLatch2. CyclicBarrier3. Semaphore 四、原子操作类五、并发工具…

dcdc buck闭环数控型稳压电源仿真+单片机程序及实验报告

资料下载地址&#xff1a;dcdc buck闭环数控型稳压电源仿真单片机程序及实验报告 一、实验目的 设计并制作一台数控型DCDC稳压电源。 二、实验要求 1、输出电压范围 &#xff1a;0.5v~4.5v。可以通过按键实现电压调整 2、必须使用PID闭环控制算法 3、发挥部分&#xff1a; PID…