AVL树的简洁写法

文章目录

    • 零、写在前面
    • 一、AVL 树定义
      • 1.1 性质
      • 1.2 树高的证明
    • 二、AVL树实现（AVL树实现名次树）
      • 2.1 节点定义
      • 2.2 左/右旋转
      • 2.3 zig-zag / zag-zig 双旋
      • 2.4 重平衡函数
      • 2.5 插入
      • 2.6 删除
      • 2.7 排名查询
      • 2.8 查前驱/后继
      • 2.9 查第 k 小
      • 2.10 完整代码
    • 三、online judge 验证
      • 3.1 P6136 【模板】普通平衡树（数据加强版）

零、写在前面

大二学数据结构的时候写的AVL代码稀烂，回过头来重制一下，在不使用父指针的情况下以较为简洁的代码实现AVL。

只是为了方便自己快速复习下AVL树原理，不作过多原理说明，详见：AVL树详解[C++]

一、AVL 树定义

AVL 树 是一种平衡二叉搜索树，由两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在1962年发明，并以他们名字的首字母命名。

1.1 性质

  1. 空二叉树是一个 AVL 树
  2. 如果 T 是一棵 AVL 树，那么其左右子树也是 AVL 树，并且 |height(lc) - height(rc) <= 1|，h 是其左右子树的高度
  3. 树高为 O(logn)

平衡因子：左子树高度 - 右子树高度

1.2 树高的证明

设 f n 为高度为 n 的 A V L 树所包含的最少节点数，则有 f n = { 1 ( n = 1 ) 2 ( n = 2 ) f n − 1 + f n − 2 + 1 ( n > 2 ) 根据常系数非齐次线性差分方程的解法 ( 或者对转移矩阵求特征向量并相似对角化 ) ， { f n + 1 } 是一个斐波那契数列。这里 f n 的通项为： f n = 5 + 2 5 5 ( 1 + 5 2 ) n + 5 − 2 5 5 ( 1 − 5 2 ) n − 1 斐波那契数列以指数的速度增长，对于树高 n 有： n < log ⁡ 1 + 5 2 ( f n + 1 ) < 3 2 log ⁡ 2 ( f n + 1 ) 因此 A V L 树的高度为 O ( log ⁡ f n ) ，这里的 f n 为结点数。 设 f_{n} 为高度为 n 的 AVL 树所包含的最少节点数，则有 \\ f_{n}=\left\{\begin{array}{ll} 1 & (n=1) \\ 2 & (n=2) \\ f_{n-1}+f_{n-2}+1 & (n>2) \end{array}\right. \\ 根据常系数非齐次线性差分方程的解法(或者对转移矩阵求特征向量并相似对角化)， \left\{f_{n}+1\right\} 是一个斐波那契数列。这里 f_{n} 的通项为： \\ f_{n}=\frac{5+2 \sqrt{5}}{5}\left(\frac{1+\sqrt{5}}{2}\right)^{n}+\frac{5-2 \sqrt{5}}{5}\left(\frac{1-\sqrt{5}}{2}\right)^{n}-1 \\ 斐波那契数列以指数的速度增长，对于树高 n 有： \\ n<\log _{\frac{1+\sqrt{5}}{2}}\left(f_{n}+1\right)<\frac{3}{2} \log _{2}\left(f_{n}+1\right) \\ 因此 AVL 树的高度为 O\left(\log f_{n}\right) ，这里的 f_{n} 为结点数。 设fn​为高度为n的AVL树所包含的最少节点数，则有fn​=⎩ ⎨ ⎧​12fn−1​+fn−2​+1​(n=1)(n=2)(n>2)​根据常系数非齐次线性差分方程的解法(或者对转移矩阵求特征向量并相似对角化)，{fn​+1}是一个斐波那契数列。这里fn​的通项为：fn​=55+25 ​​(21+5 ​​)n+55−25 ​​(21−5 ​​)n−1斐波那契数列以指数的速度增长，对于树高n有：n<log21+5 ​​​(fn​+1)<23​log2​(fn​+1)因此AVL树的高度为O(logfn​)，这里的fn​为结点数。

二、AVL树实现（AVL树实现名次树）

2.1 节点定义

struct Node {Node *l = nullptr, *r = nullptr;	// 左右儿子Key key;						// 关键字u32 h = 1;						// 高度int siz = 1;					// 子树大小Node(Key k): key(k) {}			// 构造函数
} *root = nullptr;
// 树高
int height(Node *t) {return t ? t->h : 0;
}
// 树大小
int size(Node *t) {return t ? t->siz : 0;
}
// 修正
void pull(Node *t) {t->h = std::max(height(t->l), height(t->r)) + 1;t->siz = size(t->l) + 1 + size(t->r);
}
// 平衡因子
// 根据考研408 给出的标准 height(t->l) - height(t->r)
// 其他的教材，如邓公的代码则与本文相反
int factor(Node *t) {return height(t->l) - height(t->r);
}

2.2 左/右旋转

  • 旋转不改变中序
  • 可用于单倾斜型重平衡调整
// 左旋
void rotateL(Node *&t) {Node *r = t->r;t->r = r->l;r->l = t;pull(t);pull(r);t = r;
}
// 右旋
void rotateR(Node *&t) {Node *l = t->l;t->l = l->r;l->r = t;pull(t);pull(l);t = l;
}

2.3 zig-zag / zag-zig 双旋

  • 双旋用于重平衡
// 右左双旋
void rotateRL(Node *&t) {rotateR(t->r);rotateL(t);
}
// 左右双旋
void rotateLR(Node *&t) {rotateL(t->l);rotateR(t);
}

2.4 重平衡函数

  • 在插入或者删除过程中，自顶向上回溯调整
  • 如果是 单倾斜型则单旋
  • 否则双旋
  • 两种情况，分为四种子情况，代码对偶
void reBalance(Node *&t) {int diff = factor(t);if (diff == 2) {int diff = height(t->l->l) - height(t->l->r);if (diff >= 0) {rotateR(t);} else {rotateLR(t);}} else if (diff == -2) {int diff = height(t->r->r) - height(t->r->l);if (diff >= 0) {rotateL(t);} else {rotateRL(t);}}pull(t);
}

2.5 插入

bool insert(Node *&t, Key key) {if (!t) {t = new Node(key);return true;}// 是否多重集// if (t->key == key) return false;bool res = insert(key < t->key ? t->l : t->r, key);reBalance(t);return res;
}

2.6 删除

  • 对于删除节点，找到中序后继节点替换删除即可
bool erase(Node *&t, Key key) {if (!t) return false;bool res;if (t->key == key) {if (t->l && t->r) {Node *del = t->r;while (del->l) {del = del->l;}std::swap(t->key, del->key);erase(t->r, key);}else {t = t->l ? t->l : t->r;}res = true;}else {res = erase(key < t->key ? t->l : t->r, key);}if (t) {reBalance(t);}return res;
}

2.7 排名查询

  • 定义一个关键字x的排名为 树中比 x 小的节点数 + 1
int rank(Key key) {Node *t = root;int res = 0;while (t) {if (t->key < key) {res += size(t->l) + 1;t = t->r;} else {t = t->l;}}return res + 1;
}

2.8 查前驱/后继

Node *pre(Key key) {Node *res = nullptr;Node *t = root;while (t) {if (t->key < key) {res = t;t = t->r;} else {t = t->l;}}return res;
}Node *suf(Key key) {Node *res = nullptr;Node *t = root;while (t) {if (t->key > key) {res = t;t = t->l;} else {t = t->r;}}return res;
}

2.9 查第 k 小

Node *kth(int k) {Node *res = root;while(res) {if (size(res->l) >= k) {res = res->l;} else if(size(res->l) + 1 == k) {break;} else {k -= size(res->l) + 1;res = res->r;}}return res;
}

2.10 完整代码

template<typename Key>
class AVLTree {
private:struct Node {Node *l = nullptr, *r = nullptr;Key key;u32 h = 1;int siz = 1;Node(Key k): key(k) {}} *root = nullptr;int height(Node *t) {return t ? t->h : 0;}int size(Node *t) {return t ? t->siz : 0;}void pull(Node *t) {t->h = std::max(height(t->l), height(t->r)) + 1;t->siz = size(t->l) + 1 + size(t->r);}int factor(Node *t) {return height(t->l) - height(t->r);}void rotateL(Node *&t) {Node *r = t->r;t->r = r->l;r->l = t;pull(t);pull(r);t = r;}void rotateR(Node *&t) {Node *l = t->l;t->l = l->r;l->r = t;pull(t);pull(l);t = l;}void rotateRL(Node *&t) {rotateR(t->r);rotateL(t);}void rotateLR(Node *&t) {rotateL(t->l);rotateR(t);}void reBalance(Node *&t) {int diff = factor(t);if (diff == 2) {int diff = height(t->l->l) - height(t->l->r);if (diff >= 0) {rotateR(t);} else {rotateLR(t);}} else if (diff == -2) {int diff = height(t->r->r) - height(t->r->l);if (diff >= 0) {rotateL(t);} else {rotateRL(t);}}pull(t);}bool insert(Node *&t, Key key) {if (!t) {t = new Node(key);return true;}// 是否多重集// if (t->key == key) return false;bool res = insert(key < t->key ? t->l : t->r, key);reBalance(t);return res;}bool erase(Node *&t, Key key) {if (!t) return false;bool res;if (t->key == key) {if (t->l && t->r) {Node *del = t->r;while (del->l) {del = del->l;}std::swap(t->key, del->key);erase(t->r, key);}else {t = t->l ? t->l : t->r;}res = true;}else {res = erase(key < t->key ? t->l : t->r, key);}if (t) {reBalance(t);}return res;}
public:bool insert(Key key) {return insert(root, key);}bool erase(Key key) {return erase(root, key);}int rank(Key key) {Node *t = root;int res = 0;while (t) {if (t->key < key) {res += size(t->l) + 1;t = t->r;} else {t = t->l;}}return res + 1;}Node *pre(Key key) {Node *res = nullptr;Node *t = root;while (t) {if (t->key < key) {res = t;t = t->r;} else {t = t->l;}}return res;}Node *suf(Key key) {Node *res = nullptr;Node *t = root;while (t) {if (t->key > key) {res = t;t = t->l;} else {t = t->r;}}return res;}Node *kth(int k) {Node *res = root;while(res) {if (size(res->l) >= k) {res = res->l;} else if(size(res->l) + 1 == k) {break;} else {k -= size(res->l) + 1;res = res->r;}}return res;}std::vector<Key> getAll() {std::vector<Key> res;auto dfs = [&](auto &&self, Node *t) -> void{if (!t) return;self(self, t->l);res.push_back(t->key);self(self, t->r);};dfs(dfs, root);return res;}
};

三、online judge 验证

3.1 P6136 【模板】普通平衡树（数据加强版）

题目链接

P6136 【模板】普通平衡树（数据加强版）

AC代码

#include <bits/stdc++.h>using i64 = long long;
using u32 = unsigned int;template<typename Key>
class AVLTree {
private:struct Node {Node *l = nullptr, *r = nullptr;Key key;u32 h = 1;int siz = 1;Node(Key k): key(k) {}} *root = nullptr;int height(Node *t) {return t ? t->h : 0;}int size(Node *t) {return t ? t->siz : 0;}void pull(Node *t) {t->h = std::max(height(t->l), height(t->r)) + 1;t->siz = size(t->l) + 1 + size(t->r);}int factor(Node *t) {return height(t->l) - height(t->r);}void rotateL(Node *&t) {Node *r = t->r;t->r = r->l;r->l = t;pull(t);pull(r);t = r;}void rotateR(Node *&t) {Node *l = t->l;t->l = l->r;l->r = t;pull(t);pull(l);t = l;}void rotateRL(Node *&t) {rotateR(t->r);rotateL(t);}void rotateLR(Node *&t) {rotateL(t->l);rotateR(t);}void reBalance(Node *&t) {int diff = factor(t);if (diff == 2) {int diff = height(t->l->l) - height(t->l->r);if (diff >= 0) {rotateR(t);} else {rotateLR(t);}} else if (diff == -2) {int diff = height(t->r->r) - height(t->r->l);if (diff >= 0) {rotateL(t);} else {rotateRL(t);}}pull(t);}bool insert(Node *&t, Key key) {if (!t) {t = new Node(key);return true;}// 是否多重集// if (t->key == key) return false;bool res = insert(key < t->key ? t->l : t->r, key);reBalance(t);return res;}bool erase(Node *&t, Key key) {if (!t) return false;bool res;if (t->key == key) {if (t->l && t->r) {Node *del = t->r;while (del->l) {del = del->l;}std::swap(t->key, del->key);erase(t->r, key);}else {t = t->l ? t->l : t->r;}res = true;}else {res = erase(key < t->key ? t->l : t->r, key);}if (t) {reBalance(t);}return res;}
public:bool insert(Key key) {return insert(root, key);}bool erase(Key key) {return erase(root, key);}int rank(Key key) {Node *t = root;int res = 0;while (t) {if (t->key < key) {res += size(t->l) + 1;t = t->r;} else {t = t->l;}}return res + 1;}Node *pre(Key key) {Node *res = nullptr;Node *t = root;while (t) {if (t->key < key) {res = t;t = t->r;} else {t = t->l;}}return res;}Node *suf(Key key) {Node *res = nullptr;Node *t = root;while (t) {if (t->key > key) {res = t;t = t->l;} else {t = t->r;}}return res;}Node *kth(int k) {Node *res = root;while(res) {if (size(res->l) >= k) {res = res->l;} else if(size(res->l) + 1 == k) {break;} else {k -= size(res->l) + 1;res = res->r;}}return res;}std::vector<Key> getAll() {std::vector<Key> res;auto dfs = [&](auto &&self, Node *t) -> void{if (!t) return;self(self, t->l);res.push_back(t->key);self(self, t->r);};dfs(dfs, root);return res;}
};int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n, m;std::cin >> n >> m;AVLTree<int> set;for (int i = 0; i < n; ++ i) {int x;std::cin >> x;set.insert(x);}int last = 0;int ans = 0;while(m --) {int t, x;std::cin >> t >> x;x ^= last;if (t == 1) {set.insert(x);} else if(t == 2) {set.erase(x);} else if(t == 3) {last = set.rank(x);ans ^= last;} else if(t == 4) {last = set.kth(x)->key;ans ^= last;} else if(t == 5) {last = set.pre(x)->key;ans ^= last;} else {last = set.suf(x)->key;ans ^= last;}}std::cout << ans << '\n';return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/bicheng/86909.shtml
繁体地址，请注明出处：http://hk.pswp.cn/bicheng/86909.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

红外图像增强(dde)：基于“基础层-细节层”分解的增强算法

红外图像增强(dde)：基于“基础层-细节层”分解的增强算法

1、引言 与可见光图像相比&#xff0c;红外热成像捕捉的是物体表面的温度分布&#xff0c;其原始数据&#xff08;通常为12位或14位&#xff09;包含了极宽的温度动态范围。然而&#xff0c;人眼能够感知的灰度范围以及显示设备能够展示的灰度级&#xff08;通常为8位&#xf…
阅读更多...
Java-day28-其他流

Java-day28-其他流

1. 缓冲流 昨天学习了基本的一些流&#xff0c;作为IO流的入门&#xff0c;今天我们要见识一些更强大的流。比如能够高效读写的缓冲流&#xff0c;能够转换编码的转换流&#xff0c;能够持久化存储对象的序列化流等等。这些功能更为强大的流&#xff0c;都是在基本的流对象基础…
阅读更多...
S712001 开放式用户通信

S712001 开放式用户通信

开放式用户通信分类 TIA PORTAL 软件内提供了以下指令&#xff1a; 不带连接管理的通信指令 “TCON ” &#xff1a;建立以太网连接“TDISCON” &#xff1a;断开以太网连接“TSEND” &#xff1a;TCP 和 ISO ON TCP 使用的发送数据“TRCV”&#xff1a; TCP 和 ISO ON TCP 使…
阅读更多...
CSMatIO库的安装与C#实现.mat文件生成

CSMatIO库的安装与C#实现.mat文件生成

一.CSMatIO介绍 CSMatIO 是一个用于读写 MATLAB .mat 文件的开源 C# 库&#xff0c;它提供了简单而高效的 API&#xff0c;使 .NET 应用程序能够与 MATLAB 进行数据交换&#xff0c;支持读取和写入 MATLAB 的 .mat 文件&#xff08;版本 5 和 7.3&#xff09;&#xff0c;兼容…
阅读更多...
设计一个interface (一)

设计一个interface (一)

好的&#xff0c;我来举一个具体的例子&#xff0c;帮助你理解 interface、element、resource 和 architecture 之间的关系。 场景&#xff1a;设计一个用户管理系统的接口 背景 假设我们正在设计一个用户管理系统&#xff0c;系统中有两个主要的模块&#xff1a; 用户服务模…
阅读更多...
tomcat下载安装

tomcat下载安装

目录 一.tomact简介 二.详细步骤 三.下载页面详解&#xff08;选看&#xff09; 一.tomact简介 Tomcat是Apache软件基金会下的一个核心项目&#xff0c;它是一个开源的Java Servlet和JSP容器。由Apache、Sun等公司及个人共同开发&#xff0c;由于Sun的参与&#xff0c;最新的…
阅读更多...
Axure版AntDesign 元件库-免费版

Axure版AntDesign 元件库-免费版

AntDesign 元件库概述 一、AntDesign 元件库概述 添加图片注释&#xff0c;不超过 140 字&#xff08;可选&#xff09; AntDesign 是蚂蚁集团推出的企业级设计体系&#xff0c;在 Axure 中使用 AntDesign 元件库&#xff0c;可帮助设计师快速搭建符合现代企业级产品标准的高…
阅读更多...
MySQL锁机制全解析

MySQL锁机制全解析

MYSQL存储引擎支持的锁 InnoDB支持行级锁(row-level locking)和表级锁,默认为行级锁。MyISAM采用表级锁(table-level locking) 锁的基本分类 1. 按照锁的使用方式 , Mysql的锁大致分为共享锁和排它锁 a. 共享锁(S) 共享锁&#xff0c;Share lock&#xff0c;又称为读锁&am…
阅读更多...
图解Git中Rebase与Merge的区别

图解Git中Rebase与Merge的区别

文章目录 前言理解基本概念&#x1f500; Git Merge&#xff1a;合并分支&#x1f504; Git Rebase&#xff1a;重写历史 可视化理解工作流程实际应用场景与示例场景1&#xff1a;团队协作 - 使用Merge场景2&#xff1a;个人分支整理 - 使用Rebase冲突解决&#xff1a;两种策略…
阅读更多...
2 Qt中的空窗口外观设置和常用的基础部件

2 Qt中的空窗口外观设置和常用的基础部件

Widget空窗口 this->setWindowTitle("我的窗口");//设置窗口标题this->resize(500,300);//设置窗口大小this->setFixedSize(500,300);//设置固定大小&#xff08;无法拖拽&#xff09; 此时&#xff0c;窗口大小发生改变&#xff0c;且窗口名称改变&#x…
阅读更多...
常用 Python 编辑器

常用 Python 编辑器

可以使用任何文本编辑器来编写 Python 程序&#xff0c;只要遵循 Python 语法且保存为文件&#xff0c;程序都可以通过 python 命令运行。不过&#xff0c;使用功能丰富的专用编辑器会带来更好的编程体验。 当今最常用的几个 Python 编辑器&#xff08;也称 IDE 或代码编辑器&a…
阅读更多...
Java+Vue开发的电子采购管理系统，助力企业采购智能化，提升效率促发展

Java+Vue开发的电子采购管理系统，助力企业采购智能化，提升效率促发展

前言&#xff1a; 在当今数字化时代&#xff0c;企业采购管理面临着提高效率、降低成本、增强透明度等诸多挑战。传统的采购模式往往存在流程繁琐、信息传递不及时、管理难度大等问题。电子采购管理系统应运而生&#xff0c;它借助先进的互联网技术和信息化手段&#xff0c;将…
阅读更多...
嵌入式网络通信与物联网协议全解析：Wi-Fi、BLE、LoRa、ZigBee 实战指南

嵌入式网络通信与物联网协议全解析：Wi-Fi、BLE、LoRa、ZigBee 实战指南

来源&#xff1a;0voice/EmbeddedSoftwareLearn 一、为什么嵌入式一定要搞懂网络通信&#xff1f; 在传统的裸机或单机嵌入式项目里&#xff0c;我们习惯了“点灯、串口、IC/SPI、RTOS 多任务”这样的套路。但当一个设备需要与云平台、手机 App 或其他设备实时交互时&#xff…
阅读更多...
【补充笔记●推荐方案】解决 Docker “open \.\pipe\docker_engine: Access is denied” 权限问题

【补充笔记●推荐方案】解决 Docker “open \.\pipe\docker_engine: Access is denied” 权限问题

starting services: initializing Docker API Proxy: setting up docker api proxy listener: open \\.\pipe\docker_engine: Access is denied.引言 【笔记】解决 WSL 迁移后 Docker 出现 “starting services: initializing Docker API Proxy: setting up docker ap” 问题-…
阅读更多...
AI编程工具深度对比：腾讯云代码助手CodeBuddy、Cursor与通义灵码

AI编程工具深度对比：腾讯云代码助手CodeBuddy、Cursor与通义灵码

腾讯云代码助手 CodeBuddy 智能代码补全&#xff1a;基于上下文和编辑行为预测代码&#xff0c;支持行内补全、函数块生成及注释转代码&#xff0c;覆盖200编程语言和框架&#xff0c;可减少70%以上的键盘输入。Craft智能体&#xff1a;支持自然语言驱动的多文件协同开发&…
阅读更多...
Redis 的集群

Redis 的集群

深入理解 Redis 的集群模式与高可用机制 Redis 是一款广泛应用于高性能缓存与存储系统的 NoSQL 数据库。随着业务的发展&#xff0c;如何提升 Redis 的高可用性和水平扩展能力成为架构设计的关键。本篇博客将系统讲解 Redis 的不同集群模式及其高可用策略&#xff0c;深入剖析其…
阅读更多...
基于Dify平台构建AI应用

基于Dify平台构建AI应用

2022年底openAI的chatgpt的出现&#xff0c;让人们看到生成式AI的能力如此强大&#xff0c;引燃了生成式AI的一波浪潮。2025年春节前&#xff0c;DeepSeek的横空出世让大模型这个领域变得人人都可以参与进来&#xff0c;生成式AI大模型不再有非常高的显卡的门槛&#xff0c;普通…
阅读更多...
Python tikinter实现打开指定ip的电脑摄像头

Python tikinter实现打开指定ip的电脑摄像头

以下是一个使用Python的tkinter和OpenCV库实现打开指定IP摄像头的应用程序。这个程序允许用户输入IP摄像头的URL&#xff0c;并实时显示摄像头画面&#xff0c;同时支持截图和录制功能。 登录后复制 import tkinter as tk from tkinter import ttk, messagebox, filedialog imp…
阅读更多...
OpenCV插值方法详解：原理、应用与代码实践

OpenCV插值方法详解：原理、应用与代码实践

一、引言 在数字图像处理中&#xff0c;插值是一种基本且重要的技术&#xff0c;它广泛应用于图像缩放、旋转、几何变换等场景。OpenCV作为最流行的计算机视觉库之一&#xff0c;提供了多种插值方法供开发者选择。本文将全面介绍OpenCV中的插值技术&#xff0c;包括各种方法的…
阅读更多...
创客匠人解析：身心灵赛道创始人 IP 打造核心策略

创客匠人解析：身心灵赛道创始人 IP 打造核心策略

在当代社会焦虑情绪蔓延的背景下&#xff0c;身心灵赛道正以万亿级市场规模成为知识变现的新蓝海。作为知识变现领域的重要参与者&#xff0c;创客匠人通过服务超 5W 知识博主的实践经验&#xff0c;揭示了该赛道中创始人 IP 打造的底层逻辑 ——IP 不仅是形象符号&#xff0c…
阅读更多...
最新文章

Copyright @ 2022~2023