目錄二叉搜索樹基本概念常用結論用途二叉搜索樹的性能分析二叉搜索樹的操作查找插入刪除代碼實現BSTree.hpptest.cc 二叉搜索樹 基本概念 二叉搜索樹(BST,Binary Search Tree) 二叉搜索樹又稱二叉排序樹,它或者是一棵空樹,或者是具有以下性質的二叉樹: 若它的左子樹不為空
二叉搜索樹(BST,Binary Search Tree)
二叉搜索樹又稱二叉排序樹,它或者是一棵空樹,或者是具有以下性質的二叉樹:
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
二叉搜索樹/二叉查找樹也稱二叉排序樹,因為二叉排序樹的中序遍歷結果是升序
二叉搜索樹的左子樹一定小于根,右子樹一定大于根, 結合定義遞歸子樹 可以得到
左子樹的最右節(jié)點是左子樹的最大節(jié)點,右子樹的最右節(jié)點是右子樹的最大節(jié)點.
左子樹的最左節(jié)點是左子樹的最小節(jié)點,右子樹的最左節(jié)點是右子樹的最小節(jié)點.
二叉搜索樹的最小節(jié)點是左子樹的最左節(jié)點,最大節(jié)點是右子樹的最右節(jié)點
實際情況很少直接使用搜索二叉樹,多是根據搜索二叉樹的高效搜索特性,衍生出更為實用的高階數據結構,例如平衡二叉搜索樹(AVL樹,紅黑樹)等...
還有如:門禁系統(tǒng),車庫系統(tǒng)等...
還有如:通訊錄
插入和刪除操作都必須先查找,查找效率代表了二叉搜索樹中各個操作的性能。
對有n個結點的二叉搜索樹,若每個元素查找的概率相等,則二叉搜索樹平均查找長度是結點在二叉搜索樹的深度的函數,即結點越深,則比較次數越多。
但對于同一個關鍵碼集合,如果各關鍵碼插入的次序不同,可能得到不同結構的二叉搜索樹:
最優(yōu)情況下,二叉搜索樹為完全二叉樹(或者接近完全二叉樹),其平均比較次數為:$log_2 N$ (
$log_2 N$
)
最差情況下,二叉搜索樹退化為單支樹(或者類似單支),其平均比較次數為:$\frac{N}{2}$ (
$\frac{N}{2}$
)
特別地
同樣一組數據,插入順序不同,得到的二叉樹也不同
當插入的值已存在時,插入失敗(不考慮multi)
首先查找元素是否在二叉搜索樹中,如果不存在,則返回.
否則,根據樹的結構定義,可以得到3種情況
看起來有待刪除節(jié)點有4中情況,實際情況:
要刪除的結點無孩子結點時,直接刪除
要刪除的結點只有左孩子或右孩子時,將左孩子或右孩子給父親
要刪除的結點可能是父親的左孩子或者是右孩子,有2*2種情況(要刪除的結點是父親的左孩子或右孩子)
左右孩子都是空時,也滿足情況,因此可以合并無孩子結點情況
在1的前提下,恰好是根節(jié)點,也是一種情況(讓另外一個孩子做根即可)
要刪除的結點有左右孩子(子樹)時,需要找一個既要比左子樹大也要比右子樹小的節(jié)點來補上.
根據 遞歸定義 得知,只有左孩子的最右結點和右孩子的最左結點符合條件,二選一即可
當選擇使用右孩子的最左結點時,有以下三種情況(與是不是根無關)
要刪除的結點的右子樹的最小結點恰好是要刪除結點的右孩子.
要刪除的結點的右子樹的最小結點沒有右孩子.
要刪除的結點的右子樹的最小結點有右孩子
(上圖舉例分析)
template
struct BSTreeNode {
BSTreeNode* _left;
BSTreeNode* _right;
K _key;
BSTreeNode(K key)
:_key(key),_left(nullptr),_right(nullptr)
{}
};
template
class BSTree {
public:
using Node = BSTreeNode;
BSTree() = default;
BSTree(const BSTree& bst) {
_root = Copy(bst._root);
}
BSTree& operator=(BSTree bst) { //拷貝復用
swap(_root,bst.root);
return *this;
}
~BSTree() {
Destroy(_root);
}
public:
bool Insert(const K& key) {
if (_root == nullptr) {
_root = new Node(key);
_root->_key = key;
return true;
}
BSTreeNode* cur = _root;
BSTreeNode* parent = _root;
while (cur) {
if (key < cur->_key) {
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key) {
parent = cur;
cur = cur->_right;
}
else {
return false;
}
}
//走出循環(huán),說明樹中不存在該節(jié)點, 可以插入
cur = new BSTreeNode(key);
if (key < parent->_key) {
parent->_left = cur;
}
else {
parent->_right = cur;
}
return true;
}
bool Find(const K& key) {
if (_root == nullptr) return false;
Node* cur = _root;
while (cur) {
if (key < cur->_key) {
cur = cur->_left;
}
else if (key > cur->_key) {
cur = cur->_right;
}
else {
return true;
}
}
// 從循環(huán)出來,說明沒找著
return false;
}
bool Erase(const K& key) {
if (_root == nullptr) return false;
Node* cur = _root;
Node* parent = _root;
while (cur) {
if (key < cur->_key) {
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key) {
parent = cur;
cur = cur->_right;
}
else {
//沒有左孩子
if (cur->_left == nullptr) {
if (cur == _root) {
_root = cur->_right;
}
else if (parent->_left == cur) {
parent->_left = cur->_right;
}
else {
parent->_right = cur->_right;
}
delete cur;
return true;
}
//沒有右孩子
else if (cur->_right == nullptr) {
if (cur == _root) {
_root = cur->_left;
}
if (parent->_left == cur) {
parent->_left = cur->_left;
}
else {
parent->_right = cur->_left;
}
delete cur;
return true;
}
//有左右孩子
else {
//找右孩子(子樹)的最小結點/最左結點
Node* rightMin = cur->_right; //明確不為空
Node* rightMinParent = cur;
while (rightMin->_left) {
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
// 刪除右子樹最小結點有3種情況(與是不是根無關)
//1. 要刪除的結點右子樹最小結點恰好是自己的右孩子.
//2. 要刪除的結點的右孩子的左子樹的最左結點沒有右孩子.
//3. 要刪除的結點的右孩子的左子樹的最左結點有右孩子.
//結論解析: 復用刪除單結點代碼,進行刪除rightMin即可
K tmp = rightMin->_key;
Erase(rightMin->_key); //只能從根開始遍歷,性能損失,但是二分查找很快,損失不大(理想情況,BST只學習用)
cur->_key = tmp;
return true;
} //有左右孩子的情況
} //找到了_繼續(xù)處理的過程
}//循環(huán)找的過程
//循環(huán)結束,說明沒找到
return false;
}//Erase [end]
void InOrder() {
_InOrder(_root);
std::cout << std::endl;
}
bool InsertR(const K& key) {
_InsertR(_root, key);
}
bool EraseR(const K& key) {
return _EraseR(_root,key);
}
private:
//此處返回值不能使用指針引用,雖然一定情況下可以使用(不推薦),至少目前不能引用空值.
Node* Copy(const Node* root) {
if (root == nullptr) {
return nullptr;
}
Node* newRoot = new Node(root->_key);
newRoot->_left = Copy(root->_left);
newRoot->_right = Copy(root->_right);
return newRoot;
}
//用不用引用無所謂,好習慣做到底
//(析構子節(jié)點時,父節(jié)點兩個成員會成為垂懸指針,但是接下來父親也要析構了,指針變量也隨之回收)
void Destroy(Node*&root) {
if (root == nullptr) {
return ;
}
Destroy(root->_left);
Destroy(root->_right);
std::cout<_key<<" ";
delete root; //釋放加自動置空
}
//練習遞歸+引用 -- 代碼更加簡潔
bool _EraseR(Node*& root, const K&key) {
//走到空,說明沒找到,返回false
if (root == nullptr) {
return false;
}
//大于走右邊,小于走左邊
if (key > root->_key) {
return _EraseR(root->_right,key);
}
else if(key_key) {
return _EraseR(root->_left,key);
}
//找到了
else {
if (root->_left == nullptr) {
Node* del = root;
root = root->_right;
delete del;
return true;
}
else if (root->_right == nullptr) {
Node* del = root;
root = root->_left;
delete del;
return true;
}
//有左右孩子
else {
Node* leftMax = root->_left;
//找左子樹最大結點
while (leftMax->_right) {
leftMax = leftMax->_right;
}
std::swap(root->_key, leftMax->_key);
return _EraseR(root->_left, key); //直接從左孩子開始遞歸刪除.
}
}
}
//練習遞歸+引用指針的玩法,僅練習
bool _InsertR(Node*& root, const K& key) { //引用的妙用,跨棧幀直接訪問實參
if (root == nullptr) {
root == new Node(key);
return true;
}
if (key == root->_key) return false;
return (key > root->_key) ? _InsertR(root->_right, key) : _InsertR(root->_left, key);
}
void _InOrder(Node* root) {
if (root == nullptr) return;
_InOrder(root->_left);
std::cout << root->_key << " ";
_InOrder(root->_right);
}
private:
BSTreeNode* _root = nullptr;
};
void test() {
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
BSTree bst;
for (int i : a) {
bst.Insert(i);
}
bst.InOrder();
////Find
//std::cout << std::boolalpha << bst.Find(8) << std::endl; //true
//std::cout << std::boolalpha << bst.Find(9) << std::endl; //false
BSTree cp(bst);
cp.InOrder();
//測試兩孩子的三種情況即可
bst.Erase(8); //1. 要刪除的結點的右子樹的最小結點恰好是要刪除結點的右孩子.
bst.Erase(10); //2. 要刪除的結點的右子樹的最小結點沒有右孩子
bst.Insert(5); //構造有右孩子的最小結點
bst.Erase(3); //3. 要刪除的結點的右子樹的最小結點有右孩子
bst.Erase(4);
bst.Erase(7);
bst.Erase(1);
bst.Erase(14);
bst.Erase(13);
bst.Erase(6);
bst.Erase(5);
bst.InOrder();
//禁止顯式調用析構函數 --> 雙重釋放
//bst.~BSTree();
//cp.~BSTree();
}
int main() {
test();
}
使用VSCode搭建UniApp + TS + Vue3 + Vite項目
閱讀在MDK開發(fā)環(huán)境下自定義安裝與切換不同編譯器版本的方法
閱讀musl libc 與 glibc 在 .NET 應用程序中的兼容性
閱讀受 LabelImg 啟發(fā)的基于 web 的圖像標注工具,基于 Vue 框架
閱讀光影精靈10 Win1+Ubuntu18.04 雙系統(tǒng) 踩坑記錄
閱讀LoRA模型:小型Stable Diffusion模型的微調技術
閱讀肉夾饃(Rougamo)編譯時AOP組件介紹及IoC/DI擴展
閱讀LOTO示波器統(tǒng)計曲線和故障分析pass/fail測試
閱讀