数据结构_平衡二叉树

news/2024/12/23 4:53:22/

结点类

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

相关文章

姓名详批API接口_解析姓名构成与命理特征返回json数据

姓名详批 API 接口介绍 引言 姓名在中国文化中不仅是个人的代号&#xff0c;更承载着丰富的文化内涵和命理学意义。通过分析姓名的构成&#xff0c;可以揭示个人的性格特征、运势发展及潜在的命理影响。本文将介绍一个姓名详批的 API 接口&#xff0c;提供如何通过该接口获取…

【MFC】如何修改多文档视图的标签

新建工程同之前的几篇博客 新建一个调用菜单&#xff0c;并实现其内容 以下代码演示创建时设置标题&#xff0c;并保存到子框架中 #include "MFCApplication9Doc.h" #include "MFCApplication9View.h" void CMainFrame::On32771() {CMFCApplication9Doc*…

PC寄存器(Program Counter Register)jvm

在JVM(Java虚拟机)中,PC寄存器(Program Counter Register)扮演着至关重要的角色。以下是对JVM中PC寄存器的详细解释: 一、定义与功能 定义: JVM中的PC寄存器,也被称为程序计数器,是对物理PC寄存器的一种抽象模拟。它用于存储当前线程所执行的字节码指令的地址,即指…

.NET重点

B/S C/S什么语言 B/S&#xff1a; 浏览器端&#xff1a;JavaScript&#xff0c;HTML&#xff0c;CSS 服务器端&#xff1a;ASP&#xff08;.NET&#xff09;PHP/JSP 优势&#xff1a;维护方便&#xff0c;易于升级和扩展 劣势&#xff1a;服务器负担沉重 C/S java/.NET/…

node.js的简单示例

Node.js是一个基于Chrome V8引擎的JavaScript运行时环境&#xff0c;用于方便地构建快速、可扩展的网络应用。下面是一个简单的Node.js示例&#xff0c;它创建了一个简单的HTTP服务器&#xff0c;当访问服务器时&#xff0c;它会响应“Hello World” // 引入Node.js的HTTP模块…

源码分析之Openlayers中MousePosition鼠标位置控件

概述 本文主要介绍 Openlayers 中的MousePosition鼠标位置控件&#xff0c;该控件会创建一个元素在页面的右上方用来实时显示鼠标光标的位置坐标。该控件在实际应用很有效&#xff0c;可以实时获取鼠标位置&#xff0c;但是一般控件元素都会自定义。 源码分析 MousePosition…

Spring Cloud 2023的新特性与改进

随着技术的不断演进&#xff0c;Java生态系统中的重要框架Spring也在不断更新和改进。2023年&#xff0c;Spring Cloud发布了多个新版本&#xff0c;带来了许多令人兴奋的新特性和改进。本文将深入探讨Spring Cloud 2023的新特性与改进&#xff0c;帮助开发者更好地理解和应用这…

使用Python实现基于AR的教育应用:打破课堂的墙壁

友友们好! 我的新专栏《Python进阶》正式启动啦!这是一个专为那些渴望提升Python技能的朋友们量身打造的专栏,无论你是已经有一定基础的开发者,还是希望深入挖掘Python潜力的爱好者,这里都将是你不可错过的宝藏。 在这个专栏中,你将会找到: ● 深入解析:每一篇文章都将…