当前位置: 首页 > article >正文

数据结构_平衡二叉树

结点类

构造函数分为有参和无参,相同点都是初始化树高为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.kler.cn/a/447431.html

相关文章:

  • html <a>设置发送邮件链接、打电话链接 <a href=“mailto:></a> <a href=“tel:></a>
  • UDP系统控制器_音量控制、电脑关机、文件打开、PPT演示、任务栏自动隐藏
  • 【开源免费】基于SpringBoot+Vue.JS房屋租赁管理系统(JAVA毕业设计)
  • K8s 节点 NotReady 后 Pod的变化
  • 行政管理痛点解决方案:OA系统助力企业提效减负
  • 第二十四天 循环神经网络(RNN)基本原理与实现
  • 前端面试题整理-前端异步编程
  • 【Token】校验、会话技术、登录请求、拦截器【期末实训】实战项目学生和班级管理系统\Day15-后端Web实战(登录认证)\讲义
  • ip_forward函数
  • gesp(二级)(7)洛谷:B3865:[GESP202309 二级] 小杨的 X 字矩阵
  • STM32-笔记7-继电器定时开闭
  • 雅思真题短语梳理(八)
  • 常用的JVM启动参数有哪些?
  • 电子发票汇总改名,批量处理电子发票问题
  • ChatGPT接口测试用例生成的流程
  • windows安装Elasticsearch及增删改查操作
  • 基于SpringBoot+Mysql实现的在线音乐系统平台功能实现一
  • postman测试导入文件
  • 【ETCD】【实操篇(四)】etcd常见问题快问快答FAQ
  • 2.5 io_uring
  • 黑马Java面试教程_P7_常见集合_P4_HashMap
  • homebrew,gem,cocoapod 换源,以及安装依赖
  • uniapp实现手写签名,并在app中将其转为base64格式的图片
  • springboot中的AOP以及面向切面编程思想
  • Vue.js前端框架教程8:Vue消息提示ElMessage和ElMessageBox
  • Win/Mac 如何实现测试 IP 和端口