数据结构：二叉搜索树详解

一、二叉搜索树的概念

⼆叉搜索树，它或者是⼀棵空树，或者是具有以下性质的⼆叉树:

• 任意结点左⼦树上所有结点的值都⼩于等于这个结点的值
• 任意结点右⼦树上所有结点的值都⼤于等于这个结点的值

二叉排序树的中序遍历是按照升序排列的，所以⼜称⼆叉排序树，在搜索的本职下兼职排序的任务

二、 二叉搜索树的性能分析

（一）二叉搜索树的效率

所以综合而言二叉搜索树增删查改时间复杂度为： O(N)

效率不稳定，无法达到要求，后面会继续学习平衡⼆叉搜索树AVL树和红黑树，才能高效适用于我们在内存中存储和搜索数据。

（二）数组结构和二叉排序树的比较

假如我们使用数组进行储存和搜索数据，二分查找也可以实现 O(logN) 级别的查找效率，却有不足

• 1. 需要存储在⽀持下标随机访问的结构中，并且有序。
• 2. 插⼊和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据⼀般需要挪动数据。

二叉排序树拥有兼职排序的功能和树的结构及特有性质，完美的避开了上诉的缺点。

三、二叉排序树的插入

（一）操作规则

• 1. 树为空，则直接新增结点，赋值给_root指针
• 2. 树不空，按二叉搜索树性质，插⼊值比当前结点大往右走，插⼊值比当前结点小往左走，找到空位置，插入新结点。
• 3. 如果支持插入相等的值，插⼊值跟当前结点相等的值可以按照规定往右走，也可以往左走，找到空位置，插入新结点。
     

（二）代码实现

• 递归版本

这个是之前用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;
}

四、二叉排序树的查找

（一）操作规则

• 1. 从根开始比较，查找x，x比根的值大则往右边走查找，x比根值小则往左边查找。 最多查找高度次，走到到空，还没找到，这个值不存在。
• 2. 如果不⽀持插入相等的值，找到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;};
}

结束语

这篇文章先写到这里，感谢点赞，感谢关注！