搜索二叉樹-key的搜索模型

二叉搜索樹(Binary Search Tree, BST)是一種重要的數據結構,它有兩種基本模型:Key模型和Key/Value模型。

一、Key模型

1.基本概念

?Key模型是二叉搜索樹中最簡單的形式,每個節點只存儲一個鍵值(key),沒有額外的數據值(value)。這種模型主要用于判斷某個鍵值是否存在樹中。

2.Key模型的特點:
?
- 每個節點只包含一個鍵值(key)
- 節點的鍵值必須滿足二叉搜索樹的性質:左子節點的鍵值小于父節點,右子節點的鍵值大于父節點
- 不允許鍵值重復,即樹中所有節點的鍵值都是唯一的
- 結構簡單,適用于只需要判斷元素是否存在的場景

3.典型的應用場景
?
- 單詞拼寫檢查:將字典中的所有單詞作為鍵值構建二叉搜索樹,可以快速判斷一個單詞是否正確
- 門禁系統:存儲所有授權人員的ID,快速驗證某個ID是否有權限
- 數據去重:檢查并確保集合中沒有重復元素

單詞拼寫檢查示例:

#include <iostream>
#include <string>

// 定義二叉搜索樹節點
template<class K>
struct BSTreeNode?
{
? ? BSTreeNode<K>* _left; ? // 左子節點指針
? ? BSTreeNode<K>* _right; ?// 右子節點指針
? ? K _key; ? ? ? ? ? ? ? ?// 節點存儲的鍵值

? ? // 構造函數
? ? BSTreeNode(const K& key)
? ? ? ? : _left(nullptr)
? ? ? ? , _right(nullptr)
? ? ? ? , _key(key)
? ? {}
};

// 定義二叉搜索樹類
template<class K>
class BSTree?
{
? ? typedef BSTreeNode<K> Node; ?// 節點類型別名

private:
? ? Node* _root = nullptr; ? ? ?// 根節點指針

public:
? ? // 構造函數
? ? BSTree() : _root(nullptr) {}

? ? // 析構函數
? ? ~BSTree()?
? ? {
? ? ? ? Destroy(_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;
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? Node* newNode = new Node(key);
? ? ? ? if (parent->_key < key)?
? ? ? ? {
? ? ? ? ? ? parent->_right = newNode;
? ? ? ? }
? ? ? ? else {
? ? ? ? ? ? parent->_left = newNode;
? ? ? ? }

? ? ? ? return true;
? ? }

? ? // 查找操作
? ? bool 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 true;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return false;
? ? }

private:
? ? // 銷毀樹的輔助函數
? ? void Destroy(Node* root)?
? ? {
? ? ? ? if (root)?
? ? ? ? {
? ? ? ? ? ? Destroy(root->_left);
? ? ? ? ? ? Destroy(root->_right);
? ? ? ? ? ? delete root;
? ? ? ? }
? ? }
};

int main()?
{
? ? BSTree<std::string> dictionary;

? ? // 初始化字典
? ? dictionary.Insert("apple");
? ? dictionary.Insert("banana");
? ? dictionary.Insert("cherry");
? ? dictionary.Insert("date");

? ? std::cout << "===== 單詞拼寫檢查系統 =====" << std::endl;
? ? std::cout << "已加載基礎詞典(4個單詞)\n";
? ? std::cout << "輸入要驗證的單詞(輸入 exit 退出)\n\n";

? ? std::string input;
? ? while (true)?
? ? {
? ? ? ? std::cout << "請輸入單詞: ";
? ? ? ? std::cin >> input;

? ? ? ? if (input == "exit")?
? ? ? ? {
? ? ? ? ? ? std::cout << "\n=== 感謝使用 ===" << std::endl;
? ? ? ? ? ? break;
? ? ? ? }

? ? ? ? if (dictionary.Find(input))?
? ? ? ? {
? ? ? ? ? ? std::cout << "[正確] \"" << input << "\" 存在于詞典中\n\n";
? ? ? ? }
? ? ? ? else?
? ? ? ? {
? ? ? ? ? ? std::cout << "[警告] \"" << input
? ? ? ? ? ? ? ? << "\" 未在詞典中找到,請注意拼寫!\n\n";
? ? ? ? }
? ? }

? ? return 0;
}

?二、Key/Value模型

1.基本概念

Key/Value模型是二叉搜索樹的重要擴展形式,每個節點存儲鍵值對(key-value pair),支持通過key快速查找對應的value。這種模型是構建字典、索引等數據結構的核心基礎。

2.核心特性
?
1.?鍵值對存儲:每個節點存儲唯一的key及其關聯的value
2.?排序依據:仍然基于key維持二叉搜索樹性質
3.?動態更新:允許通過相同key更新value
4.?高效查詢:保持O(logN)平均查找時間復雜度

3.應用場景

-單詞解釋

-統計水果出現次數

統計水果出現次數代碼示例:

#include <iostream>
#include <string>
#include <algorithm> // 用于大小寫轉換

// 定義二叉搜索樹節點
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;
? ? Node* _root = nullptr;

? ? // 遞歸銷毀子樹
? ? void Destroy(Node* root)?
? ? {
? ? ? ? if (root)
? ? ? ? {
? ? ? ? ? ? Destroy(root->_left);
? ? ? ? ? ? Destroy(root->_right);
? ? ? ? ? ? delete root;
? ? ? ? }
? ? }

? ? // 遞歸中序遍歷打印
? ? void _PrintInOrder(Node* root) const?
? ? {
? ? ? ? if (root)?
? ? ? ? {
? ? ? ? ? ? _PrintInOrder(root->_left);
? ? ? ? ? ? std::cout << " " << root->_key << " : " << root->_value << "\n";
? ? ? ? ? ? _PrintInOrder(root->_right);
? ? ? ? }
? ? }

public:
? ? BSTree() = default;

? ? ~BSTree()?
? ? {
? ? ? ? Destroy(_root);
? ? }

? ? // 插入或遞增計數
? ? void InsertOrIncrement(const K& key)
? ? {
? ? ? ? if (!_root)?
? ? ? ? {
? ? ? ? ? ? _root = new Node(key, 1);
? ? ? ? ? ? return;
? ? ? ? }

? ? ? ? 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?
? ? ? ? ? ? {
? ? ? ? ? ? ? ? ++cur->_value;
? ? ? ? ? ? ? ? return;
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? Node* newNode = new Node(key, 1);
? ? ? ? if (parent->_key < key)?
? ? ? ? {
? ? ? ? ? ? parent->_right = newNode;
? ? ? ? }
? ? ? ? else {
? ? ? ? ? ? parent->_left = newNode;
? ? ? ? }
? ? }

? ? // 打印統計結果
? ? void PrintStatistics() const?
? ? {
? ? ? ? std::cout << "\n===== 水果統計結果 =====\n";
? ? ? ? _PrintInOrder(_root);
? ? ? ? std::cout << "=======================\n";
? ? }
};

int main()?
{
? ? BSTree<std::string, int> fruitCounter;

? ? std::cout << "=== 水果統計系統 ===\n"
? ? ? ? << "輸入水果名稱進行統計(輸入'q'結束)\n"
? ? ? ? << "(自動轉換為小寫,支持大小寫混合輸入)\n\n";

? ? std::string input;
? ? while (true)
? ? {
? ? ? ? std::cout << "輸入水果名稱: ";
? ? ? ? std::cin >> input;

? ? ? ? // 轉換為小寫
? ? ? ? std::transform(input.begin(), input.end(), input.begin(),
? ? ? ? ? ? [](unsigned char c) { return std::tolower(c); });

? ? ? ? if (input == "q") break;

? ? ? ? fruitCounter.InsertOrIncrement(input);
? ? }

? ? // 輸出統計結果
? ? fruitCounter.PrintStatistics();

? ? return 0;
}

單詞解釋代碼示例:

#include <iostream>
#include <string>

// 定義二叉搜索樹節點
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; ?// 節點類型別名

private:
? ? Node* _root = nullptr; ? ? ?// 根節點指針

public:
? ? // 構造函數
? ? BSTree() : _root(nullptr) {}

? ? // 析構函數
? ? ~BSTree()?
? ? {
? ? ? ? Destroy(_root);
? ? }

? ? // 插入操作
? ? bool Insert(const K& key, const V& value)?
? ? {
? ? ? ? if (!_root) { ?// 空樹情況
? ? ? ? ? ? _root = new Node(key, value);
? ? ? ? ? ? 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 { ?// 鍵值已存在,更新value
? ? ? ? ? ? ? ? cur->_value = value;
? ? ? ? ? ? ? ? return false;
? ? ? ? ? ? }
? ? ? ? }

? ? ? ? // 創建新節點并插入
? ? ? ? Node* newNode = new Node(key, value);
? ? ? ? if (parent->_key < key)?
? ? ? ? {
? ? ? ? ? ? parent->_right = newNode;
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? parent->_left = newNode;
? ? ? ? }

? ? ? ? return true;
? ? }

? ? // 查找操作
? ? V* 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->_value;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return nullptr; ?// 查找失敗
? ? }

private:
? ? // 銷毀樹的輔助函數
? ? void Destroy(Node* root)
? ? {
? ? ? ? if (root)?
? ? ? ? {
? ? ? ? ? ? Destroy(root->_left);
? ? ? ? ? ? Destroy(root->_right);
? ? ? ? ? ? delete root;
? ? ? ? }
? ? }
};


int main()?
{
? ? BSTree<std::string, std::string> dict;

? ? // 構建詞典
? ? dict.Insert("apple", "A round fruit with red, green, or yellow skin and a white inside.");
? ? dict.Insert("banana", "A long curved fruit with yellow skin and soft sweet flesh.");

? ? // 交互查詢
? ? std::string word;
? ? while (true)?
? ? {
? ? ? ? std::cout << "Enter word to lookup (q to quit): ";
? ? ? ? std::cin >> word;
? ? ? ? if (word == "q") break;

? ? ? ? if (auto def = dict.Find(word))?
? ? ? ? {
? ? ? ? ? ? std::cout << "Definition: " << *def << "\n\n";
? ? ? ? }
? ? ? ? else?
? ? ? ? {
? ? ? ? ? ? std::cout << "Word not found. Add definition? (y/n) ";
? ? ? ? ? ? char choice;
? ? ? ? ? ? std::cin >> choice;
? ? ? ? ? ? if (choice == 'y')?
? ? ? ? ? ? {
? ? ? ? ? ? ? ? std::string newDef;
? ? ? ? ? ? ? ? std::cout << "Enter definition: ";
? ? ? ? ? ? ? ? std::cin.ignore();
? ? ? ? ? ? ? ? std::getline(std::cin, newDef);
? ? ? ? ? ? ? ? dict.Insert(word, newDef);
? ? ? ? ? ? ? ? std::cout << "Added!\n\n";
? ? ? ? ? ? }
? ? ? ? }
? ? }

? ? return 0;
}

碼字不易,求關注

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/bicheng/78439.shtml
繁體地址,請注明出處:http://hk.pswp.cn/bicheng/78439.shtml
英文地址,請注明出處:http://en.pswp.cn/bicheng/78439.shtml

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

相關文章

安卓四大組件之ContentProvider

目錄 實現步驟 代碼分析 onCreate insert query ContextHolder Cursor 作用與用法 基本步驟&#xff1a; 可能的面試題&#xff1a;為什么使用Cursor&#xff1f; 為什么使用Cursor 使用Cursor的好處 靜態內部類實現單例模式 AnndroidManifest.xml配置信息 注釋的…

【HTML】【Web開發】滑動條挑戰

最近在思考如何開發一些入門級的迷你游戲&#xff0c;于是抽空寫了個HTML的滑動條小游戲。 游戲規則如下&#xff1a; 在[0, 100]區間內隨機生成一個目標值&#xff0c;顯示為&#xff1a;X% 倒計時 3 秒過后&#xff0c;出現 10 秒的挑戰倒計時和【停止】按鈕 挑戰倒計時結…

面試踩過的坑

1、 “”和equals 的區別 “”是運算符&#xff0c;如果是基本數據類型&#xff0c;則比較存儲的值&#xff1b;如果是引用數據類型&#xff0c;則比較所指向對象的地址值。equals是Object的方法&#xff0c;比較的是所指向的對象的地址值&#xff0c;一般情況下&#xff0c;重…

專業軟件開發全流程實踐指南

作為一家擁有十余年行業積淀的專業軟件開發服務提供商&#xff0c;我們見證了太多項目從無到有的全過程。今天&#xff0c;我們就用最樸實的語言&#xff0c;跟大家聊聊一個軟件產品從構思到上線的完整歷程。這些經驗不僅適用于自建技術團隊的企業&#xff0c;對正在尋找軟件外…

聊透多線程編程-線程互斥與同步-12. C# Monitor類實現線程互斥

目錄 一、什么是臨界區&#xff1f; 二、Monitor類的用途 三、Monitor的基本用法 四、Monitor的工作原理 五、使用示例1-保護共享變量 解釋&#xff1a; 六、使用示例2-線程間信號傳遞 解釋&#xff1a; 七、注意事項 八、總結 在多線程編程中&#xff0c;線程之間的…

第R4周:LSTM-火災溫度預測

文章目錄 一、前期準備工作1.導入數據2. 數據集可視化 二、構建數據集1. 數據集預處理2. 設置X, y3. 劃分數據集 三、模型訓練1. 構建模型2. 定義訓練函數3. 定義測試函數4. 正式訓練模型 四、模型評估1. Loss圖片2. 調用模型進行預測3. R2值評估 總結&#xff1a; &#x1f36…

toCharArray作用

toCharArray() 是 Java 中 String 類的一個方法&#xff0c;其作用是將字符串對象轉換為一個字符數組。下面為你詳細介紹其用法、原理和示例。 方法定義 toCharArray() 方法在 java.lang.String 類里被定義&#xff0c;方法簽名如下 public char[] toCharArray() 此方法沒有…

STM32八股【6】-----CortexM3的雙堆棧(MSP、PSP)設計

STM32的線程模式&#xff08;Thread Mode&#xff09;和內核模式&#xff08;Handler Mode&#xff09;以及其對應的權級和堆棧指針 線程模式&#xff1a; 正常代碼執行時的模式&#xff08;如 main 函數、FreeRTOS任務&#xff09; 可以是特權級&#xff08;使用MSP&#xff…

驅動支持的最高CUDA版本與實際安裝的Runtime版本

查看電腦上安裝的CUDA版本的多種方法&#xff0c;適用于不同系統和場景。 方法一&#xff1a;通過命令行工具 1. 查看CUDA Driver API版本&#xff08;顯卡驅動支持的CUDA版本&#xff09; 命令&#xff1a;nvidia-smi操作&#xff1a; 打開終端&#xff08;Windows為CMD/Pow…

Python CT圖像預處理——基于ITK-SNAP

Python CT圖像預處理——nii格式讀取、重采樣、窗寬窗位設置_python讀取nii-CSDN博客 基于原文指出以下幾個問題&#xff1a;文件路徑設置模糊&#xff1b;nilabel里面使用的get_data() 方法已經過時&#xff1b;需要導入scikit-image&#xff0c;還要導入一個matplotlib。 一…

【MQ篇】RabbitMQ之消息持久化!

目錄 一、 交換機持久化 (Exchange Persistence)二、 隊列持久化 (Queue Persistence)三、 消息持久化 (Message Persistence)四、 持久化的“黃金三角” &#x1f531;&#xff1a;三者缺一不可&#xff01;五、 來&#xff0c;完整的代碼示例&#xff08;整合持久化和確認機制…

[AI技術(二)]JSONRPC協議MCPRAGAgent

Agent概述(一) AI技術基礎(一) JSON-RPC 2.0 協議詳解 JSON-RPC 2.0 是一種基于 JSON 的輕量級遠程過程調用(RPC)協議,旨在簡化跨語言、跨平臺的遠程通信。以下從協議特性、核心結構、錯誤處理、批量請求等角度進行詳細解析: 一、協議概述 1. 設計原則 ? 簡單性:…

LeetCode238_除自身以外數組的乘積

LeetCode238_除自身以外數組的乘積 標簽&#xff1a;#數組 #前綴和Ⅰ. 題目Ⅱ. 示例0. 個人方法一&#xff1a;暴力循環嵌套0. 個人方法二&#xff1a;前綴和后綴分別求積 標簽&#xff1a;#數組 #前綴和 Ⅰ. 題目 給你一個整數數組 nums&#xff0c;返回 數組 answer &#…

算法筆記.spfa算法(bellman-ford算法的改進)

題目&#xff1a;&#xff08;來源于AcWing&#xff09; 給定一個 n 個點 m 條邊的有向圖&#xff0c;圖中可能存在重邊和自環&#xff0c; 邊權可能為負數。 請你求出 1 號點到 n 號點的最短距離&#xff0c;如果無法從 1 號點走到 n 號點&#xff0c;則輸出 impossible。 …

07 Python 字符串全解析

文章目錄 一. 字符串的定義二. 字符串的基本用法1. 訪問字符串中的字符2. 字符串切片3. 字符串拼接4. 字符串重復5.字符串比較6.字符串成員運算 三. 字符串的常用方法1. len() 函數2. upper() 和 lower() 方法3. strip() 方法4. replace() 方法5. split() 方法 四. 字符串的進階…

Java集成Zxing和OpenCV實現二維碼生成與識別工具類

Java集成Zxing和OpenCV實現二維碼生成與識別工具類 本文將介紹如何使用Java集成Zxing和OpenCV庫&#xff0c;實現二維碼的生成和識別功能。識別方法支持多種輸入形式&#xff0c;包括File對象、文件路徑和Base64編碼。 一、環境準備 添加Maven依賴 <dependencies><…

【專題刷題】二分查找(二)

&#x1f4dd;前言說明&#xff1a; 本專欄主要記錄本人的基礎算法學習以及LeetCode刷題記錄&#xff0c;按專題劃分每題主要記錄&#xff1a;&#xff08;1&#xff09;本人解法 本人屎山代碼&#xff1b;&#xff08;2&#xff09;優質解法 優質代碼&#xff1b;&#xff…

Java—ThreadLocal底層實現原理

首先&#xff0c;ThreadLocal 本身并不提供存儲數據的功能&#xff0c;當我們操作 ThreadLocal 的時候&#xff0c;實際上操作線程對象的一個名為 threadLocals 成員變量。這個成員變量的類型是 ThreadLocal 的一個內部類 ThreadLocalMap&#xff0c;它是真正用來存儲數據的容器…

Elasticsearch(ES)中的腳本(Script)

文章目錄 一. 腳本是什么&#xff1f;1. lang&#xff08;腳本語言&#xff09;2. source&#xff08;腳本代碼&#xff09;3. params&#xff08;參數&#xff09;4. id&#xff08;存儲腳本的標識符&#xff09;5. stored&#xff08;是否為存儲腳本&#xff09;6. script 的…

客戶聯絡中心能力與客戶匹配方式

在數字化時代&#xff0c;客戶聯絡中心作為企業與客戶溝通的核心樞紐&#xff0c;其服務能力與客戶需求的精準匹配至關重要。隨著客戶期望的不斷提升&#xff0c;傳統的“一刀切”服務模式已難以滿足個性化需求&#xff0c;如何通過智能化的手段實現服務能力與客戶的高效匹配&a…