数据结构之搜索二叉树

一、什么是搜索二叉树

基本概念

特点

注意事项

二、搜索二叉树的C++实现

2.0 构造与析构

2.1 插入

2.2 查找

2.3 删除

2.3.1 无牵无挂型

2.3.2 独生子女型

2.3.3 儿女双全型

三、搜索二叉树的应用

3.1 key搜索

3.2 key/value搜索

一、什么是搜索二叉树

搜索二叉树，通常称为二叉搜索树（BST，Binary Search Tree），是一种特殊的二叉树数据结构。

基本概念

节点结构：二叉搜索树由一系列节点组成，每个节点包含一个键值（用于比较）和一个与之关联的值。
树结构：每个节点最多有两个子节点，分别称为左子节点和右子节点。

特点

有序性：二叉搜索树的核心特点是有序性。对于树中的任意节点：
所有左子树的节点键值均小于该节点的键值。
所有右子树的节点键值均大于该节点的键值。
查找效率：由于有序性，二叉搜索树可以在对数时间内（树的高度次）完成查找、插入和删除操作，即时间复杂度为O(log n)，其中n是树中节点的数量。
动态性：二叉搜索树支持动态数据集合的操作，允许在运行时添加或删除元素。

注意事项

当二叉搜索树不平衡时，其性能可能会退化到接近线性时间复杂度O(n)，此时可能需要使用平衡二叉搜索树（如AVL树或红黑树）来保证操作的效率。具体请关注博主后续博客

二、搜索二叉树的C++实现

2.0 构造与析构

template<class K>
struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}
};

~BSTree()
{Destroy(_root);_root = nullptr;
}
//递归删除
void Destroy(Node* root)
{if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;
}

BSTree(const BSTree& t)
{_root = Copy(t._root);
}BSTree& operator=(BSTree tmp)
{swap(_root, tmp._root);return *this;
}
//递归复制
Node* Copy(Node* root)
{if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;
}

2.1 插入

思路

树为空，则直接新增结点，赋值给root指针
树不空，按⼆叉搜索树性质，插入值比当前结点⼤往右⾛，插入值比当前结点小往左⾛，找到空位置，插⼊新结点。
如果⽀持插⼊相等的值，插⼊值跟当前结点相等的值可以往右⾛，也可以往左⾛，找到空位置，插入新结点。

难点

为提升效率，不采用递归做法，采用循环模拟递归
二叉搜索树的性质决定了必有一个空节点会存放当前key值
为了维持二叉搜索树的性质，需要额外引入parent指针。最后插入的位置需要与parent所指向的值进行比对，决定插入在左子树还是右子树。

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 true;}}node* newnode = new node(key);if (parent->_key > key){parent->_left = newnode;}else{parent->_right = newnode;}return true;
}

2.2 查找

思路

从根开始⽐较，查找x，⽐根的值⼤则往右边⾛，⽐根值⼩则往左边⾛。
最多查找⾼度次，⾛到到空，还没找到，这个值不存在。
本文实现不支持插入冗余值（模拟实现STL库中的set）
如果要模拟实现STL库中的multiset，STL库中实现的是返回中序遍历的第一个相等的节点

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;
}

2.3 删除

删除有如下三种情况

2.3.1 无牵无挂型

把结点的⽗亲对应孩⼦指针指向空，直接删除N结点

2.3.2 独生子女型

把N结点的⽗亲对应孩⼦指针指向N的右/左孩⼦，直接删除N结点

2.3.3 儿女双全型

采用替代法：

找左子树的最⼤结点(最右结点)或者右子树的最⼩结点(最左结点)替代N，直接复制值替代即可
然后转成删除替代节点

bool Erase(const K& key)
{node* parent = nullptr;node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}//删除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;}// 如果右为空else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{// 左右都不为空// 右子树最左节点Node* replaceParent = cur;Node* replace = cur->_right;while (replace->_left){replaceParent = replace;replace = replace->_left;}cur->_key = replace->_key;//最左节点依然可能有最右节点if (replaceParent->_left == replace)replaceParent->_left = replace->_right;elsereplaceParent->_right = replace->_right;delete replace;}return true;}}return false;
}

三、搜索二叉树的应用

3.1 key搜索

Key搜索指的是使用“key”（关键字或关键项）作为检索依据来快速查找和检索数据的过程。在二叉搜索树中，通过比较节点的Key与要查找的Key，可以确定搜索方向（向左或向右），直到找到匹配的节点或确定目标不存在。

3.2 key/value搜索

Key/Value搜索是一种基于键值对（Key-Value Pair）的数据检索方式。在这种模式下，数据被组织成一系列的键值对，每个键值对由一个唯一的键（Key）和一个与之相关联的值（Value）组成。搜索时，用户通过提供键来查询对应的值。

Key/Value搜索的实现方式常用的有以下几种

哈希表：
哈希表是实现Key/Value搜索的一种常见数据结构。通过哈希函数将键映射到表的某个位置，以快速定位到对应的值。
B树及其变种：
在一些需要持久化存储的Key/Value数据库中，可能会使用B树（如B+树）或其变种来存储数据。这些数据结构通过保持数据的有序性来优化搜索和范围查询的性能。
分布式哈希表：
在分布式系统中，分布式哈希表（DHT）是一种用于实现Key/Value搜索的分布式数据结构。它通过将键分散到多个节点上来实现数据的分布式存储和检索。

本文介绍用二叉搜索树实现key/value搜索

#pragma once
#include<iostream>
using namespace std;namespace key_value
{template<class K, class V>struct BSTNode{K _key;V _value;BSTNode<K, V>* _left;BSTNode<K, V>* _right;BSTNode(const K& key, const V& value):_key(key), _value(value), _left(nullptr), _right(nullptr){}};template<class K, class V>class BSTree{typedef BSTNode<K> Node;public:// 强制生成构造BSTree() = default;BSTree(const BSTree& t){_root = Copy(t._root);}BSTree& operator=(BSTree tmp){swap(_root, tmp._root);return *this;}~BSTree(){Destroy(_root);_root = nullptr;}bool Insert(const K& key, const V& value){if (_root == nullptr){_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{return false;}}cur = new Node(key, value);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return 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* 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 (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{Node* replaceParent = cur;Node* replace = cur->_right;while (replace->_left){replaceParent = replace;replace = replace->_left;}cur->_key = replace->_key;if (replaceParent->_left == replace)replaceParent->_left = replace->_right;elsereplaceParent->_right = replace->_right;delete replace;}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);}//递归删除void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}//递归复制Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}private:Node* _root = nullptr;};
}