[ 数据结构进阶 - C++ ] 二叉搜索树 BSTree - JOYK Joy of Geek, Geek News, Link all geek

到如今，C++的基本语法已经了解过了。在之前，数据结构初阶是使用C语言实现的，我们进入进阶数据结构之后，将使用C++语言来实现。本篇文章我们将学习了解二叉搜索树- 二叉树的进阶。

1.二叉搜索树

1.1二叉搜索树的概念

二叉搜索数又称二叉排序树（BST，Binary Search Tree），它或者是一颗空树，或者是有以下性质的二叉树：

若它的左子树不为空，则左子树上的所有节点的值都小于根节点的值。
若它的右子树不为空，则右子树上的所有节点的值都大于根节点的值。
它的左右子树也分别为二叉搜索树。

我们看两个实际的例子

1.这不是一颗二叉搜索树，因为红圈部分中，5作为7的右子树，并没有满足右子树大于根节点。

2.这是一颗二叉搜索树，树中任意一颗子树也构成二叉搜索树。满足左节点比根节点小，右节点比根节点大的性质

1.2 二叉搜索树的操作

二叉树的实现在文章附录（模拟实现，包含全部结构）

1.2.1 二叉搜索树的查找

a.从根节点开始比较，查找，比根节点大的往右边查找，比跟小的往左边查找

b.最多查找高度次，走到空若还没找到，这个值不存在。

1.查找的非递归方法：

bool Find(const{
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.查找的递归方法:

bool _FindR(Node* root, const K& key)
{
if (root == nullptr)
return false;

if (root->_key < key)
{
return _FindR(root->_right, key);
}
else if (root->_key > key)
{
return _FindR(root->_left, key);
}
else
{
return true;
}
}

1.2.2 二叉搜索树的插入

二叉搜索树的插入具体过程：

a.树为空，则直接新增节点，赋值给root指针。

b.树不为空，按二叉搜索树性质查找插入位置，插入新节点。

我们以下图二叉树为例：对这个课树插入12

我们在插入前需要考虑的事情以及处理方法:

插入成功的情况：

1.如果该树为空，则new一个节点，让其为根，插入成功。

2.如果该树不为空，则进行遍历找到自己属于的位置，new一个节点，赋值12，插入成功。

3.在找到自己的位置之后，我们还需要将改节点连在原树上面，因此需要一个parent节点，来判断这颗节点是parent的左孩子还是右孩子。

插入失败的情况：

1.由于性质所说，左子树均小于根节点，右子树均大于根节点，因此对于这种情况是不存在值相同的两个节点。因此一旦树中已经存在该节点，则插入失败。

考虑这些之后，我们便可以写出一个非递归版本的insert

//插入
bool Insert(const{
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 < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}

insert的递归有点难，先不写了

1.2.3 二叉树的删除

二叉树的删除要查找元素是否在二叉搜索树中，如果不存在，则返回，否则要删除的结点可能分为下面四种情况：

a.要删除的节点无孩子节点

b.要删除的节点只有左孩子节点

c.要删除的节点只有右孩子节点

d.要删除的节点有左，右孩子节点

在这四种情况中，情况a和情况b或情况c可以算是一种情况。因为如果节点无孩子的时候，不写a情况，也会进入b情况和c情况。

因此可以分为：

a.该节点没有左孩子

b.该节点没有右孩子

c.该节点有两个孩子

我们首先看a情况的实现细节：

1.该节点没有左孩子

假如要删除这颗二叉树的10节点和4节点

我们依然是使用parent节点作为cur的父节点，cur为查询指针。当cur找到10节点后，如果左为空则为该种情况：

（1）如果该节点是根节点，则让根节点等于他的右孩子节点

（2）如果cur == parent->right （删除10的情况），则让parent->right = cur->right即可

（3）如果cur == parent->left （删除4的情况），则让parent->left = cur->right即可

（4）最后delete cur即可。

if (cur->_left == nullptr)
{
//判断跟
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (cur == parent->_right)
{
//cur 比 parent大
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
delete

这部分代码为核心删除代码，全代码当删除情况讲完时呈现。

2.该节点没有右孩子

假设要删除节点14 ，逻辑和删除左孩子类似，只要掌握好链接关系即可

else if (cur->_right == nullptr)
{
//判断跟
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (cur == parent->_right)
{
//cur 比 parent大
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
delete

3.该节点有左右两个孩子

如果删除的节点有两个孩子，则选择在他的右子树中寻找中序的第一个节点，也就是右子树的最小值进行替换，也可以选择左子树的最大值。例如这颗子树，要删除3和删除10

此时需要进行节点替换，找到3节点中右子树最小的节点，然后两个节点的值进行交换，定义MinParNode = cur,MinNode，首先让MinNode指向3的右孩子，然后一直向左边找，找到节点的next为空时，则该节点就是最小的节点。此时让3和该节点进行交换。

交换完毕后，删除3就变成了删除刚刚交换的最小的节点，也就是MinNode。我们查询MinNode和MinParNode的指向关系，如果MinParNode的左孩子是MinNode，则让MinParNode的左指向MinNode的右，如果是右孩子，则让MinParNode的右指向MinNode的右。（这里为什么是MinParNode的右边指向孩子的呢？是因为MinNode已经是最小的节点了，他不可能有左孩子了，但是如果是删除10这种情况，右孩子还是有节点的，所以直接指向右解决了所有的情况）。

非递归删除代码：

bool Erase(const{
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
{
//找到了
// 1. 该节点没有左孩子
// 2. 该节点没有右孩子
if (cur->_left == nullptr)
{
//判断跟
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (cur == parent->_right)
{
//cur 比 parent大
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->_right)
{
//cur 比 parent大
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
delete cur;
}
else
{
//有两个节点，替换
Node* MinParNode = cur;
Node* MinNode = cur->_right;
while (MinNode->_left)
{
MinParNode = MinNode;
MinNode = MinNode->_left;
}
swap(cur->_key, MinNode->_key);
//if (MinNode->_right != nullptr)//自己写的错误的
if(MinParNode->_left == MinNode)//老师写的
{
MinParNode->_left = MinNode->_right;
}
else
{
MinParNode->_right = MinNode->_right;
}
delete MinNode;
}

return true;
}
}
return false;
}

2.二叉搜索树的应用

2.1 K模型

K模型即只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值。

我们上述实现的就是K模型。

2.2 KV模型

KV模型的模拟实现在附录页

kv模型：每一个关键码key，都有预支对应的值Value，即<key，value>的键值对。这种方法也有很多使用的情况。

比如英汉词典是英文与中文的对应关系，我们可以使用KV模型，存放<word,chinese>构成键值对

3.二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树的各个操作的性能。

对于n个节点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是节点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

但对于同一个关键码结合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树，

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：log_2 N

最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：N

改进：如果退化成单支树，二叉搜索树的性能就失去了，因此后续我们将对二叉搜索树的插入规则进行修改，将实现出平衡二叉搜索树AVL树及其红黑树（RB树）。

1.二叉搜索树的模拟实现（K模型）

//二叉搜索树结点的结构
template <class K>
struct BSTreeNode
{
BSTreeNode* _left;
BSTreeNode* _right;

K _key;//值

BSTreeNode(const K& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}

};

//二叉树的结构
template <class K>
class BSTree
{
typedef BSTreeNode<K> Node;//结点重命名为Node
private:
//递归思想析构
void DestoryTree(Node* root){
if (root == nullptr)
return;
DestoryTree(root->_left);
DestoryTree(root->_right);
delete root;
}
Node* CopyTree(Node* root){
if (root == nullptr)
return nullptr;
Node* copynode = new Node(root->_key);
copynode->_left = CopyTree(root->_left);
copynode->_right = CopyTree(root->_right);

return copynode;
}
public:
//强制编译器自己生成构造
//C++
BSTree() = default;

BSTree(const BSTree<K>& t)
{
_root = CopyTree(t._root);
}

//t1 = t2
BSTree<K>& operator=(BSTree<K> t)
{
swap(_root, t._root);
return *this;
}

~BSTree()
{
DestoryTree(_root);
_root = nullptr;
}
//插入
bool Insert(const{
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 < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}

bool Find(const{
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{
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
{
//找到了
// 1. 该节点没有左孩子
// 2. 该节点没有右孩子
if (cur->_left == nullptr)
{
//判断跟
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (cur == parent->_right)
{
//cur 比 parent大
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->_right)
{
//cur 比 parent大
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
delete cur;
}
else
{
//有两个节点，替换
Node* MinParNode = cur;
Node* MinNode = cur->_right;
while (MinNode->_left)
{
MinParNode = MinNode;
MinNode = MinNode->_left;
}
swap(cur->_key, MinNode->_key);
//if (MinNode->_right != nullptr)//自己写的错误的
if(MinParNode->_left == MinNode)//老师写的
{
MinParNode->_left = MinNode->_right;
}
else
{
MinParNode->_right = MinNode->_right;
}
delete MinNode;
}

return true;
}
}
return false;
}
//中序遍历
void InOrder(){
_InOrder(_root);
}

//////////////////////////////////////////////////
//递归方法
bool FindR(const{
return _FindR(_root, key);
}

bool InsertR(const{
return _InsertR(_root, key);
}

bool EraseR(const{
return _EraseR(_root, key);
}

private:
//不好理解暂时还没理解
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* MinNode = root->_right;
while (MinNode->_left)
{
MinNode = MinNode->_left;
}
swap(root->_key, MinNode->_key);

return _EraseR(root->_right, key);
}
delete del;
return true;
}
}
bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}

if (root->_key < key)
{
return _InsertR(root->_right, key);
}
else if (root->_key > key)
{
return _InsertR(root->_left, key);
}
else
{
//说明这个值已经存在了就不再插入了
return false;
}
}
//这里之间 InsertR好理解 EraseR暂时不好理解
bool _FindR(Node* root, const K& key)
{
if (root == nullptr)
return false;

if (root->_key < key)
{
return _FindR(root->_right, key);
}
else if (root->_key > key)
{
return _FindR(root->_left, key);
}
else
{
return true;
}
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}

private:
Node* _root = nullptr;
};

2.KV模型模拟实现

template<class K, class V>
struct BSTreeNode
{
BSTreeNode<K, V>* _left;
BSTreeNode<K, V>* _right;

const 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:

void InOrder(){
_InOrder(_root);
cout << endl;
}

///////////////////////////////////////////////////////////////////////////////
Node* FindR(const{
return _FindR(_root, key);
}

bool InsertR(const K& key, const{
return _InsertR(_root, key, value);
}

bool EraseR(const{
return _EraseR(_root, key);
}

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

swap(root->_key, minRight->_key);

return _EraseR(root->_right, key);
}

delete del;
return true;
}
}

bool _InsertR(Node*& root, const K& key, const V& value)
{
if (root == nullptr)
{
root = new Node(key, value);
return true;
}

if (root->_key < key)
return _InsertR(root->_right, key, value);
else if (root->_key > key)
return _InsertR(root->_left, key, value);
else
return false;
}

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

void _InOrder(Node* root)
{
if (root == nullptr)
return;

_InOrder(root->_left);
cout << root->_key << ":" << root->_value << endl;
_InOrder(root->_right);
}
private:
Node* _root = nullptr;
};

（本篇完）

[ 数据结构进阶 - C++ ] 二叉搜索树 BSTree

1.二叉搜索树

1.1二叉搜索树的概念

1.2 二叉搜索树的操作

1.2.1 二叉搜索树的查找

1.2.2 二叉搜索树的插入

1.2.3 二叉树的删除

3.该节点有左右两个孩子

2.二叉搜索树的应用

2.1 K模型

2.2 KV模型

3.二叉搜索树的性能分析

1.二叉搜索树的模拟实现（K模型）

2.KV模型模拟实现

Recommend

月均GMV超500万，快手“小叶子”以精细化运营打开纸品销售新格局

SUSE 与亚马逊云科技建立全新战略合作加速 SAP 云端创新

开源分析数据库ClickHouse和开源esProc SPL的性能对比

英伟达 RTX 40 系列显卡发售；拼多多海外暂不上线砍一刀；李佳琦复播，商品不见一线大...

被逼无奈的乐视，走上新东方直播的老路

Kostenfreies Webseminar: SAP Data Warehouse Cloud & SAP BW Bridge: Berechtig...

东软教育与普洱学院共建数字产业学院，聚焦新技术、新业态与信息技术的深度融合

Elucidata's MLOps platform boosts data quality for drug discovery | VentureBeat

Apple Watch Ultra: 10 New and Noteworthy Features

Chainlink 联合创始人：区块链和智能合约将推动信任最小化

About Joyk