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?為高度為nAVL樹所包含的最少節點數,則有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
英文地址,請注明出處:http://en.pswp.cn/bicheng/86909.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

紅外圖像增強(dde):基于“基礎層-細節層”分解的增強算法

1、引言 與可見光圖像相比&#xff0c;紅外熱成像捕捉的是物體表面的溫度分布&#xff0c;其原始數據&#xff08;通常為12位或14位&#xff09;包含了極寬的溫度動態范圍。然而&#xff0c;人眼能夠感知的灰度范圍以及顯示設備能夠展示的灰度級&#xff08;通常為8位&#xf…

Java-day28-其他流

1. 緩沖流 昨天學習了基本的一些流&#xff0c;作為IO流的入門&#xff0c;今天我們要見識一些更強大的流。比如能夠高效讀寫的緩沖流&#xff0c;能夠轉換編碼的轉換流&#xff0c;能夠持久化存儲對象的序列化流等等。這些功能更為強大的流&#xff0c;都是在基本的流對象基礎…

S712001 開放式用戶通信

開放式用戶通信分類 TIA PORTAL 軟件內提供了以下指令&#xff1a; 不帶連接管理的通信指令 “TCON ” &#xff1a;建立以太網連接“TDISCON” &#xff1a;斷開以太網連接“TSEND” &#xff1a;TCP 和 ISO ON TCP 使用的發送數據“TRCV”&#xff1a; TCP 和 ISO ON TCP 使…

CSMatIO庫的安裝與C#實現.mat文件生成

一.CSMatIO介紹 CSMatIO 是一個用于讀寫 MATLAB .mat 文件的開源 C# 庫&#xff0c;它提供了簡單而高效的 API&#xff0c;使 .NET 應用程序能夠與 MATLAB 進行數據交換&#xff0c;支持讀取和寫入 MATLAB 的 .mat 文件&#xff08;版本 5 和 7.3&#xff09;&#xff0c;兼容…

設計一個interface (一)

好的&#xff0c;我來舉一個具體的例子&#xff0c;幫助你理解 interface、element、resource 和 architecture 之間的關系。 場景&#xff1a;設計一個用戶管理系統的接口 背景 假設我們正在設計一個用戶管理系統&#xff0c;系統中有兩個主要的模塊&#xff1a; 用戶服務模…

tomcat下載安裝

目錄 一.tomact簡介 二.詳細步驟 三.下載頁面詳解&#xff08;選看&#xff09; 一.tomact簡介 Tomcat是Apache軟件基金會下的一個核心項目&#xff0c;它是一個開源的Java Servlet和JSP容器。由Apache、Sun等公司及個人共同開發&#xff0c;由于Sun的參與&#xff0c;最新的…

Axure版AntDesign 元件庫-免費版

AntDesign 元件庫概述 一、AntDesign 元件庫概述 添加圖片注釋&#xff0c;不超過 140 字&#xff08;可選&#xff09; AntDesign 是螞蟻集團推出的企業級設計體系&#xff0c;在 Axure 中使用 AntDesign 元件庫&#xff0c;可幫助設計師快速搭建符合現代企業級產品標準的高…

MySQL鎖機制全解析

MYSQL存儲引擎支持的鎖 InnoDB支持行級鎖(row-level locking)和表級鎖,默認為行級鎖。MyISAM采用表級鎖(table-level locking) 鎖的基本分類 1. 按照鎖的使用方式 , Mysql的鎖大致分為共享鎖和排它鎖 a. 共享鎖(S) 共享鎖&#xff0c;Share lock&#xff0c;又稱為讀鎖&am…

圖解Git中Rebase與Merge的區別

文章目錄 前言理解基本概念&#x1f500; Git Merge&#xff1a;合并分支&#x1f504; Git Rebase&#xff1a;重寫歷史 可視化理解工作流程實際應用場景與示例場景1&#xff1a;團隊協作 - 使用Merge場景2&#xff1a;個人分支整理 - 使用Rebase沖突解決&#xff1a;兩種策略…

2 Qt中的空窗口外觀設置和常用的基礎部件

Widget空窗口 this->setWindowTitle("我的窗口");//設置窗口標題this->resize(500,300);//設置窗口大小this->setFixedSize(500,300);//設置固定大小&#xff08;無法拖拽&#xff09; 此時&#xff0c;窗口大小發生改變&#xff0c;且窗口名稱改變&#x…

常用 Python 編輯器

可以使用任何文本編輯器來編寫 Python 程序&#xff0c;只要遵循 Python 語法且保存為文件&#xff0c;程序都可以通過 python 命令運行。不過&#xff0c;使用功能豐富的專用編輯器會帶來更好的編程體驗。 當今最常用的幾個 Python 編輯器&#xff08;也稱 IDE 或代碼編輯器&a…

Java+Vue開發的電子采購管理系統,助力企業采購智能化,提升效率促發展

前言&#xff1a; 在當今數字化時代&#xff0c;企業采購管理面臨著提高效率、降低成本、增強透明度等諸多挑戰。傳統的采購模式往往存在流程繁瑣、信息傳遞不及時、管理難度大等問題。電子采購管理系統應運而生&#xff0c;它借助先進的互聯網技術和信息化手段&#xff0c;將…

嵌入式網絡通信與物聯網協議全解析:Wi-Fi、BLE、LoRa、ZigBee 實戰指南

來源&#xff1a;0voice/EmbeddedSoftwareLearn 一、為什么嵌入式一定要搞懂網絡通信&#xff1f; 在傳統的裸機或單機嵌入式項目里&#xff0c;我們習慣了“點燈、串口、IC/SPI、RTOS 多任務”這樣的套路。但當一個設備需要與云平臺、手機 App 或其他設備實時交互時&#xff…

【補充筆記●推薦方案】解決 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與通義靈碼

騰訊云代碼助手 CodeBuddy 智能代碼補全&#xff1a;基于上下文和編輯行為預測代碼&#xff0c;支持行內補全、函數塊生成及注釋轉代碼&#xff0c;覆蓋200編程語言和框架&#xff0c;可減少70%以上的鍵盤輸入。Craft智能體&#xff1a;支持自然語言驅動的多文件協同開發&…

Redis 的集群

深入理解 Redis 的集群模式與高可用機制 Redis 是一款廣泛應用于高性能緩存與存儲系統的 NoSQL 數據庫。隨著業務的發展&#xff0c;如何提升 Redis 的高可用性和水平擴展能力成為架構設計的關鍵。本篇博客將系統講解 Redis 的不同集群模式及其高可用策略&#xff0c;深入剖析其…

基于Dify平臺構建AI應用

2022年底openAI的chatgpt的出現&#xff0c;讓人們看到生成式AI的能力如此強大&#xff0c;引燃了生成式AI的一波浪潮。2025年春節前&#xff0c;DeepSeek的橫空出世讓大模型這個領域變得人人都可以參與進來&#xff0c;生成式AI大模型不再有非常高的顯卡的門檻&#xff0c;普通…

Python tikinter實現打開指定ip的電腦攝像頭

以下是一個使用Python的tkinter和OpenCV庫實現打開指定IP攝像頭的應用程序。這個程序允許用戶輸入IP攝像頭的URL&#xff0c;并實時顯示攝像頭畫面&#xff0c;同時支持截圖和錄制功能。 登錄后復制 import tkinter as tk from tkinter import ttk, messagebox, filedialog imp…

OpenCV插值方法詳解:原理、應用與代碼實踐

一、引言 在數字圖像處理中&#xff0c;插值是一種基本且重要的技術&#xff0c;它廣泛應用于圖像縮放、旋轉、幾何變換等場景。OpenCV作為最流行的計算機視覺庫之一&#xff0c;提供了多種插值方法供開發者選擇。本文將全面介紹OpenCV中的插值技術&#xff0c;包括各種方法的…

創客匠人解析:身心靈賽道創始人 IP 打造核心策略

在當代社會焦慮情緒蔓延的背景下&#xff0c;身心靈賽道正以萬億級市場規模成為知識變現的新藍海。作為知識變現領域的重要參與者&#xff0c;創客匠人通過服務超 5W 知識博主的實踐經驗&#xff0c;揭示了該賽道中創始人 IP 打造的底層邏輯 ——IP 不僅是形象符號&#xff0c…