数据结构：二叉搜索树详解
二叉搜索树详解
- 一、二叉搜索树的概念
- 二、 二叉搜索树的性能分析
- （一）二叉搜索树的效率
- （二）数组结构和二叉排序树的比较
- 三、二叉排序树的插入
- （一）操作规则
- （二）代码实现
- 四、二叉排序树的查找
- （一）操作规则
- （二）代码实现
- 五、二叉排序树的删除
- （一）操作规则
- （二）代码实现
- 六、二叉搜索树key_value使用
- 七、完整源代码
- 结束语
一、二叉搜索树的概念
⼆叉搜索树，它或者是⼀棵空树，或者是具有以下性质的⼆叉树:
- 任意结点左⼦树上所有结点的值都⼩于等于这个结点的值
- 任意结点右⼦树上所有结点的值都⼤于等于这个结点的值
二叉排序树的中序遍历是按照升序排列的，所以⼜称⼆叉排序树，在搜索的本职下兼职排序的任务
二、 二叉搜索树的性能分析
（一）二叉搜索树的效率
所以综合而言二叉搜索树增删查改时间复杂度为： O(N)
效率不稳定，无法达到要求，后面会继续学习平衡⼆叉搜索树AVL树和红黑树，才能高效适用于我们在内存中存储和搜索数据。
（二）数组结构和二叉排序树的比较
假如我们使用数组进行储存和搜索数据，二分查找也可以实现 O(logN) 级别的查找效率，却有不足
-
- 需要存储在⽀持下标随机访问的结构中，并且有序。
-
- 插⼊和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据⼀般需要挪动数据。
二叉排序树拥有兼职排序的功能和树的结构及特有性质，完美的避开了上诉的缺点。
三、二叉排序树的插入
（一）操作规则
-
- 树为空，则直接新增结点，赋值给
_root指针
- 树为空，则直接新增结点，赋值给
-
- 树不空，按二叉搜索树性质，插⼊值比当前结点大往右走，插⼊值比当前结点小往左走，找到空位置，插入新结点。
-
- 如果支持插入相等的值，插⼊值跟当前结点相等的值可以按照规定往右走，也可以往左走，找到空位置，插入新结点。
- 如果支持插入相等的值，插⼊值跟当前结点相等的值可以按照规定往右走，也可以往左走，找到空位置，插入新结点。
（二）代码实现
- 递归版本
这个是之前用C语言实现的二叉排序树的插入，当时觉得设计的已经十分巧妙，现在学了C++,使用了更加可维护，高效率的方式实现，也就是下面的非递归。
#define KEY(n) (n ? n->key : -1)
typedef struct Node {
int key;
struct Node *lchild, *rchild;
} Node;
Node *getNewNode(int key) {
Node *p = (Node *)malloc(sizeof(Node));
p->key = key;
p->lchild = p->rchild = NULL;
return p;
}
Node *insert(Node *root, int key) {
if (root == NULL) return getNewNode(key);
if (key == root->key) return root;
if (key < root->key) root->lchild = insert(root->lchild, key);
else root->rchild = insert(root->rchild, key);
return root;
}
- 非递归版本
首先传参使用const和&加以修饰，在遍历的时候，需要使用parent来记录一下cur前一个结点的位置。
bool insert(const K& key)
{
if (_root == nullptr) {
_root = new Node(key);
return true;
}
Node* parent = nullptr, * 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 (key < parent->_key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
四、二叉排序树的查找
（一）操作规则
-
- 从根开始比较，查找x，x比根的值大则往右边走查找，x比根值小则往左边查找。 最多查找高度次，走到到空，还没找到，这个值不存在。
-
- 如果不⽀持插入相等的值，找到x即可返回，如果⽀持插入相等的值，意味着可能有多个x存在，⼀般要求查找中序的第⼀个x。
（二）代码实现
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;
}
五、二叉排序树的删除
（一）操作规则
查找元素是否在⼆叉搜索树中，如果不存在，则返回false，反之就进行下面的操作。
（二）代码实现
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->_right)
{
parent->_right = cur->_right;
}
else
{
parent->_left = 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;
}
}
delete cur;
}
else
{
Node* minRightParent = cur;
Node* minRight = cur->_right;
while (minRight->_left)
{
minRightParent = minRight;
minRight = minRight->_left;
}
cur->_key = minRight->_key;
if (minRightParent->_left == minRight)
{
minRightParent->_left = minRight->_right;
}
else
{
minRightParent->_right = minRight->_right;
}
delete minRight;
}
return true;
}
}
return false;
}
六、二叉搜索树key_value使用
key_value仍然是二叉搜索树，只是此时除了键值以外还多了一个绑定的值，这个值可以是任何类型。增/删/查还是以key为关键字按照二叉排序树的规则进行，可以通过快速查找到key对应的value,同时达到一种映射关系。key/value的搜索场景实现的二叉树搜索树支持修改value
- 场景1：简单中英互译字典，树的结构中(结点)存储key(英文)和vlaue(中文)，搜索时输⼊英⽂，则同时查找到了英文对应的中文。
- 场景2：商场无人值守⻋库，入口进场时扫描⻋牌，记录⻋牌和入场时间，出口离场时，扫描⻋牌，查找⼊场时间，当前时间-入场时间计算出停车时长，计算出停车费用，缴费后抬杆，车辆离场。
- 场景3：统计⼀篇⽂章中单词出现的次数，读取⼀个单词，查找单词是否存在，不存在这个说明第⼀次出现，（单词，1），单词存在，则++单词对应的次数。
七、完整源代码
#pragma once
#include<iostream>
using namespace std;
namespace key {
template<class K>
struct BSTNode
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
BSTNode(const K& key)
:_key(key)
,_left(nullptr)
,_right(nullptr)
{}
};
template<class K>
class BSTree {
typedef BSTNode<K> Node;
public:
bool insert(const K& key)
{
if (_root == nullptr) {
_root = new Node(key);
return true;
}
Node* parent = nullptr, *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 (key < parent->_key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
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;
}
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->_right)
{
parent->_right = cur->_right;
}
else
{
parent->_left = 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;
}
}
delete cur;
}
else
{
Node* minRightParent = cur;
Node* minRight = cur->_right;
while (minRight->_left)
{
minRightParent = minRight;
minRight = minRight->_left;
}
cur->_key = minRight->_key;
if (minRightParent->_left == minRight)
{
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 << " ";
_InOrder(root->_right);
}
Node* _root = nullptr;
};
}
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, V> Node;
public:
bool insert(const K& key, const V& value)
{
if (_root == nullptr) {
_root = new Node(key, value);
return true;
}
Node* parent = nullptr, * 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 (key < parent->_key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
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;
}
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->_right)
{
parent->_right = cur->_right;
}
else
{
parent->_left = 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;
}
}
delete cur;
}
else
{
Node* minRightParent = cur;
Node* minRight = cur->_right;
while (minRight->_left)
{
minRightParent = minRight;
minRight = minRight->_left;
}
cur->_key = minRight->_key;
if (minRightParent->_left == minRight)
{
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);
}
Node* _root = nullptr;
};
}
结束语
这篇文章先写到这里，感谢点赞，感谢关注！