網站首頁 編程語言 正文
二叉搜索樹概念與操作
二叉搜索樹的概念
二叉搜索樹又稱二叉排序樹，若它的左子樹不為空，則左子樹上所有節點的值都小于根節點的值；若它的右子樹不為空，則右子樹上所有節點的值都大于根節點的值，它的左右子樹也分別未二叉搜索樹。也可以是一顆空樹。
int a[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
二叉搜索樹的操作
查找
迭代：
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
遞歸：
Node* _FindR(Node* root, const K& key)
{
if (root == nullptr)
return nullptr;
if (root->_key < key)
return _FindR(root->_right, key);
else if (root->_key > key)
return _FindR(root->_left, key);
else
return root;
}
插入
樹為空，則直接插入
樹不為空，按二叉搜索樹性質查找插入位置，插入新節點
迭代：
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
//查找要插入的位置
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(key);
if (parent->_key < cur->_key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
遞歸：
bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
else
{
if (root->_key < key)
{
return _InsertR(root->_left, key);
}
else if (root->_key > key)
{
return _InsertR(root->_left, key);
}
else
{
return false;
}
}
}
刪除
首先查找元素是否在二叉搜索樹中，如果不存在，則返回，否則要刪除的結點可能分下面四種情況：
- 要刪除的結點無孩子結點
- 要刪除的結點只有左孩子結點
- 要刪除的結點只有右孩子結點
- 要刪除的結點只有左、右結點
實際情況中1和2或3可以合并，因此真正的刪除過程如下：
- 刪除該結點且使被刪除結點的雙親結點指向被刪除結點的左孩子結點
- 刪除該結點且使被刪除結點的雙親結點指向被刪除結點的右孩子結點
- 替代法。在它的右子樹中尋找中序下的第一個結點（關鍵碼最小），用它的值填補到被刪除結點中，再來處理該結點的刪除問題。
迭代：
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
//刪除
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
}
else
{
//找到右樹最小節點去替代刪除
Node* minRightParent = cur;
Node* minRight = cur->_right;
while (minRight->_left)
{
minRightParent = minRight;
minRight = minRight->_left;
}
cur->_key = minRight->_key;
if (minRight == minRightParent->_left)
minRightParent->_left = minRight->_right;
else
minRightParent->_right = minRight->_right;
delete minRight;
}
return true;
}
}
return false;
}
遞歸：
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
return false;
if (root->_key < key)
{
return _EraseR(root->_right, key);
}
else if (root->_key > key)
{
return _EraseR(root->_left, key);
}
else
{
//刪除
Node* del = root;
if (root->_left == nullptr)
{
root = root->_right;
}
else if (root->_right == nullptr)
{
root = root->_left;
}
else
{
//替代法刪除
Node* minRight = root->_right;
while (minRight->_left)
{
minRight = minRight->_left;
}
root->_key = minRight->_key;
//轉換成遞歸在右子樹中刪除最小節點
return _EraseR(root->_right, minRight->_key);
}
delete del;
return true;
}
}
二叉搜索樹的應用
1.K模型：K模型即只有key作為關鍵碼，結構中只需要存儲key即可，關鍵碼即為需要搜索到的值。比如：給一個單詞word，判斷該單詞是否拼寫正確。具體方法如下：1.以單詞集合中的每個單詞作為key，構建一棵二叉搜索樹。2.在二叉搜索樹中檢索該單詞是否存在，存在則拼寫正確，不存在則拼寫錯誤。
2.KV模型：每一個關鍵碼key，都有與之對應的值Value，即<Key, Value>的鍵值對。該種方式在現實生活中非常常見：比如英漢詞典就是英語與中文的對應關系，通過英文可以快速找到與其對應的中文，英文單詞與其對應的中文<word, chinese>就構成一種鍵值對；再比如統計單詞次數，統計成功后，給定單詞就可快速找到其出現的次數，單詞與其出現次數就是<word, count>就構成一種鍵值對。
比如：實現一個簡單的英漢詞典dict，可以通過英文找到與其對應的中文，具體實現方式如下：1.<單詞，中文含義>為鍵值對構造二叉搜索樹，注意：二叉搜索樹需要比較，鍵值對比較時只比較Key。2.查詢英文單詞時，只需要給出英文單詞，就可快速找到與其對應的Key。
namespace KEY_VALUE {
template<class K, class V>
struct BSTreeNode
{
BSTreeNode<K, V>* _left;
BSTreeNode<K, V>* _right;
K _key;
V _value;
BSTreeNode(const K& key, const V& value)
:_left(nullptr)
,_right(nullptr)
,_key(key)
,_value(value)
{}
};
template<class K, class V>
class BSTree {
typedef BSTreeNode<K, V> Node;
public:
V& operator[](const K& key)
{
pair<Node*, bool> ret = Insert(key, V());
return ret.first->_value;
}
pair<Node*, bool> Insert(const K& key, const V& value)
{
if (_root == nullptr)
{
_root = new Node(key, value);
return make_pair(_root, true);
}
//查找要插入的位置
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return make_pair(cur, false);
}
}
cur = new Node(key, value);
if (parent->_key < cur->_key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return make_pair(cur, true);
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
bool Erase(const K& key)
{
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
//刪除
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else
{
//找到右樹最小結點去替代刪除
Node* minRightParent = cur;
Node* minRight = cur->_left;
while (minRight->_left)
{
minRightParent = minRight;
minRight = minRight->_left;
}
cur->_key = minRight->_key;
if (minRight = minRightParent->_left)
minRightParent->_left = minRight->right;
else
minRightParent->_right = minRight->_right;
delete minRight;
}
return true;
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << ":" << root->_value << endl;
_InOrder(root->_right);
}
private:
Node* _root = nullptr;
};
}
void Test2()
{
KEY_VALUE::BSTree<string, string> dict;
dict.Insert("sort", "排序");
dict.Insert("insert", "插入");
dict.Insert("tree", "樹");
dict.Insert("right", "右邊");
string str;
while (cin >> str)
{
if (str == "q")
{
break;
}
else
{
auto ret = dict.Find(str);
if (ret == nullptr)
{
cout << "拼寫錯誤，請檢查你的單詞" << endl;
}
else
{
cout << ret->_key <<"->"<< ret->_value << endl;
}
}
}
}
void Test3()
{
//統計字符串出現次數，也是經典key/value
string str[] = { "sort", "sort", "tree", "insert", "sort", "tree", "sort", "test", "sort" };
KEY_VALUE::BSTree<string, int> countTree;
//for (auto& e : str)
//{
// auto ret = countTree.Find(e);
// if (ret == nullptr)
// {
// countTree.Insert(e, 1);
// }
// else
// {
// ret->_value++;
// }
//}
for (auto& e : str)
{
countTree[e]++;
}
countTree.InOrder();
}
二叉樹的性能分析
插入和刪除操作都必須先查找，查找效率代表了二叉搜索樹中各個操作的性能。
對有n個結點的二叉搜索樹，若每個元素查找的概率相等，則二叉搜索樹平均查找長度是結點在二叉搜索樹的深度的函數，即結點越深，比較的次數越多。
但對于同一個關鍵碼集合，如果關鍵碼插入的次序不同，可能得到不同結構的二叉搜索樹
最優情況下，二叉搜索樹為完全二叉樹，其平均比較次數為：logN
最差情況下，二叉搜索樹退化為單支樹，其平均比較次數為：N/2
原文鏈接：https://blog.csdn.net/mmz123_/article/details/122722192
相關推薦
- 2024-01-16 where語句后跟case語句
- 2022-09-24 C#中ref關鍵字的用法_C#教程
- 2022-02-07 使用laravel框架開發接口時post請求報錯419，get請求正常
- 2022-06-26 Android界面一鍵變灰開發深色適配模式編程示例_Android
- 2022-01-11 小程序 ------ [mini-css-extract-plugin] css沖突問題
- 2022-03-14 easypoi導入校驗跳過空行_EasyPoi導入驗證功能
- 2022-12-09 ReactQuery系列React?Query?實踐示例詳解_React
- 2022-06-06 PyTorch?device與cuda.device用法介紹_python
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速