二叉搜素树简单介绍

二叉搜索树又称二叉排序树，是具有以下性质的二叉树:

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为二叉搜索树

注意：空树也是二叉搜索树

---

二叉搜素树的模型

K模型：

K模型即<code>只有key作为关键字，节点中只需要存储Key即可，关键字即为需要搜索到的值。

比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：

以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树

在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

KV模型：

每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。

该种方式在现实生活中非常常见：

比如

英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；

再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出

现次数就是<word, count>就构成一种键值对。

K模式和KV模式实现上基本一样，就是节点中存储的是key还是<key,val>的区别

---

二叉搜素树的性能

二叉搜索树的性能取决于树的高度，因为一次查找最多查找高度次，而删除和插入也是在查找的基础上增加了一些O(1)的操作

在最理想的情况下，树是完全平衡的，平均查找、插入和删除的时间复杂度O(log N)。

但在最坏的情况下，树可能退化成一个链表，此时这些操作的时间复杂度将增加到O(N)。

例：

---

全部的实现代码放在了文章末尾

准备工作

创建两个文件，一个头文件<code>BSTree.hpp，一个源文件test.cpp

【因为模板的声明和定义不能分处于不同的文件中，所以把成员函数的声明和定义放在了同一个文件BSTree.hpp中】

RBTree.hpp：存放包含的头文件，命名空间的定义，成员函数和命名空间中的函数的定义

test.cpp：存放main函数，以及测试代码

---

包含头文件

iostream：用于输入输出

---

类的成员变量

---

构造函数和拷贝构造

构造函数没什么好说的，默认构造就行了

<code>BSTree()

:_root(nullptr)

{ -- -->}

拷贝构造：

因为节点都是从堆区new出来的，所以要深拷贝

使用递归实现深拷贝：

因为拷贝构造不能有多余的参数，但是递归函数又必须使用参数记录信息

所以再封装一个成员函数，专门用来递归拷贝：

然后在拷贝构造里面调用一下这个函数就行了

<code>拷贝构造

BSTree(const BSTree& obj)

{ -- -->

_root = Copy(obj._root);

}

---

swap和赋值运算符重载

交换两颗二叉搜索树的本质就是交换两颗数的资源（数据），而它们的资源都是从堆区申请来的，然后用指针指向这些资源

<code>并不是把资源存储在了二叉搜索树对象中

所以资源交换很简单，直接交换_root指针的指向即可

void Swap(BSTree& obj)

{ -- -->

std::swap(_root, obj._root);

}

---

赋值运算符重载

BSTree& operator=(BSTree obj)

{

this->Swap(obj);

return *this;

}

为什么上面的两句代码就可以完成深拷贝呢？

这是因为：

使用了传值传参，会在传参之前调用拷贝构造，再把拷贝构造出的临时对象作为参数传递进去

赋值运算符的左操作数，*this再与传入的临时对象obj交换，就直接完成了拷贝

在函数结束之后，存储在栈区的obj再函数结束之后，obj生命周期结束

obj调用析构函数，把指向的从*this那里交换来的不需要的空间销毁

---

析构函数

使用递归遍历，把所有从堆区申请的节点都释放掉：

因为析构函数不能有多余的参数，但是递归函数又必须使用参数记录信息

所以再封装一个成员函数，专门用来递归释放：

然后在拷贝构造里面调用一下这个函数就行了

<code>析构函数

~BSTree()

{ -- -->

Destroy(_root);

_root = nullptr;

}

---

find

具体流程：

从根节点开始，将目标值（传入的key）与当前节点的key进行比较。

如果目标值小于当前节点值，则在左子树中继续查找；

如果目标值大于当前节点值，则在右子树中继续查找。

这个过程一直进行，直到找到与目标值或者到达空节点为止。

把上述过程转成代码：

---

insert

插入的具体过程如下：

树为空，则直接新增节点，赋值给二叉搜索树的成员变量<code>_root指针

树不空，则按照查找（find）的逻辑找到新节点应该插入的位置

树不空，如果树中已经有了一个节点的key值与要插入的节点的key相同，就插入失败

这个过程一直进行，直到找到与传入的key相等的节点或者到达空节点为止。

把上述过程转成代码：

---

erase

删除操作较为复杂，需要先在数中找到要删除的节点，再根据要删除节点的子节点数量进行不同的处理：

如果要删除节点没有子节点，则直接删除该节点。

如果要删除节点有一个子节点（子树），则用其子节点（子树）替换该节点。

如果要删除节点有两个子节点（子树）

在右子树中找到最小值的节点（或左子树中找到最大值的节点）来替换待删除节点，然后删除那个最小值（或最大值）的节点

情况1可以和情况2合并一下

把上述过程转成代码：

<code>bool Erase(const K& key)

{ -- -->

Node* cur = _root;从根节点开始

Node* parent = nullptr;

先找到要删除的节点（cur）

while (cur)如果到了空节点就结束循环

{

if (cur->_key < key) 目标值`大于`当前节点值，则在`右子树`中继续查找

{

parent = cur;

cur = cur->_right;

}

else if (cur->_key > key) 目标值'小于'当前节点值，则在'左子树'中继续查找

{

parent = cur;

cur = cur->_left;

}

else

{

break;找到要删除的节点了，结束循环

}

}

如果找到空节点了，还没找到要删除的节点

就说明树里面本来就没有这个key，不需要删除

if (cur == nullptr)

{

return false; 删除失败，返回false

}

else

{

如果 左 子树为空， 右 子树不为空（或者左右都为空)

即只有右子节点（右子树）或者没有子节点

if (cur->_left == nullptr)

{

如果父亲节点为空，就表示cur为根节点

if (parent == nullptr)

{

使用右子节点，代替根节点

_root = cur->_right;

}

else 根据cur与它的父亲节点的链接关系

{

if (cur == parent->_left)

{

使用右子节点，代替cur

parent->_left = cur->_right;

}

else

{

使用右子节点，代替cur

parent->_right = cur->_right;

}

}

delete cur; 删除cur节点，即要删除的节点

}

如果 右 子树为空， 左 子树不为空（或者左右都为空)

即只有左子节点（左子树）或者没有子节点

else if (cur->_right == nullptr)

{

如果父亲节点为空，就表示cur为根节点

if (parent == nullptr)

{

使用左子节点，代替根节点

_root = cur->_left;

}

else 根据cur与它的父亲节点的链接关系

{

if (cur == parent->_left)

{

使用左子节点，代替cur

parent->_left = cur->_left;

}

else

{

使用左子节点，代替cur

parent->_right = cur->_left;

}

}

delete cur; 删除cur节点，即要删除的节点

}

else 如果左右子树都不为nullptr

{

去cur（要删除的节点）的右子树中找key最小的节点

Node* tmp = cur->_right;

Node* prev = cur;

二叉搜索树的最小节点，一定在这颗树的最左边

while (tmp->_left) 所以一直往左走，直到左子树为nullptr

{

prev = tmp;

tmp = tmp->_left; 往左走

}

用右子树中key最小的节点的数据，替换cur中的数据

也就相当于把cur（要删除的节点）删除了

cur->_key = tmp->_key;

cur->_val = tmp->_val;

如果prev == cur，就说明tmp就是key最小的节点了

此时tmp在cur(prev)的右边

if (prev == cur)

{

把cur(prev)的 右边 连上tmp的右子树

因为tmp虽然是最左节点，但是它有可能还有右孩子

cur->_right = tmp->_right;

delete tmp;

}

else

{

把prev的 左边 连上tmp的右子树

因为tmp虽然是最左节点，但是它有可能还有右孩子

prev->_left = tmp->_right;

delete tmp;

}

}

}

return true; 删除成功，返回true

}

---

empty

bool Empty()

{

如果_root为空，那么树就是空的

return _root == nullptr;

}

---

size

使用递归实现二叉搜索树的节点个数统计：

因为我们经常使用的stl的容器的size都是没有参数的，但是递归函数又必须使用参数记录信息

所以再封装一个成员函数，专门用来递归：

然后再size里面调用一下就行了

<code>size_t Size()

{ -- -->

return _Size(_root);

}

---

中序遍历

中序遍历的递归函数：

然后再调用递归函数

<code>void InOrder()

{ -- -->

_InOrder(_root);

}

---

全部代码

#include<iostream>

using namespace std;

template<class K, class V>

struct BSTreeNode

{

K _key;

V _val;

BSTreeNode<K, V>* _left;

BSTreeNode<K, V>* _right;

BSTreeNode(const K& key, const V& val)

:_left(nullptr)

, _right(nullptr)

{

_key = key;

_val = val;

}

};

template<class K, class V>

class BSTree

{

typedef BSTreeNode<K, V> Node;

public:

BSTree() :_root(nullptr)

{ }

BSTree(const BSTree& obj)

{

_root = Copy(obj._root);

}

BSTree& operator=(BSTree obj)

{

this->Swap(obj);

return *this;

}

~BSTree()

{

Destroy(_root);

_root = nullptr;

}

void Swap(BSTree& obj)

{

std::swap(_root, obj._root);

}

bool Insert(const K& key, const V& val)

{

if (_root == nullptr)//树为空，则直接新增节点

{

//赋值给二叉搜索树的成员变量`_root`指针

_root = new Node(key, val);

return true;//返回true，代表插入成功

}

Node* cur = _root;//从根节点开始

//定义parent来保存cur的父亲节点

//假设根节点的父亲节点为nullptr

Node* parent = nullptr;

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, val);

if (parent->_key > key)

{

parent->_left = newnode;

}

else

{

parent->_right = newnode;

}

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;//找不到就返回nullptr

}

bool Erase(const K& key)

{

Node* cur = _root;

Node* parent = nullptr;

while (cur)

{

if (cur->_key < key)

{

parent = cur;

cur = cur->_right;

}

else if (cur->_key > key)

{

parent = cur;

cur = cur->_left;

}

else

{

break;

}

}

if (cur == nullptr)

return false;

else

{

if (cur->_left == nullptr)

{

if (parent == nullptr)

{

_root = cur->_right;

}

else

{

if (cur == parent->_left)

parent->_left = cur->_right;

else

parent->_right = cur->_right;

}

delete cur;

}

else if (cur->_right == nullptr)

{

if (parent == nullptr)

{

_root = cur->_left;

}

else

{

if (cur == parent->_left)

parent->_left = cur->_left;

else

parent->_right = cur->_left;

}

delete cur;

}

else

{

Node* tmp = cur->_right;

Node* prev = cur;

while (tmp->_left)

{

prev = tmp;

tmp = tmp->_left;

}

cur->_key = tmp->_key;

cur->_val = tmp->_val;

if (prev == cur)

{

cur->_right = tmp->_right;

delete tmp;

}

else

{

prev->_left = tmp->_right;

delete tmp;

}

}

}

return true;

}

void InOrder()

{

_InOrder(_root);

}

bool Empty()

{

return _root == nullptr;

}

size_t Size()

{

return _Size(_root);

}

size_t Height()

{

return _Height(_root);

}

private:

Node* _root = nullptr;

size_t _Height(Node* root)

{

if (root == nullptr)

return 0;

int left = _Height(root->_left);

int right = _Height(root->_right);

return left > right ? left + 1 : right + 1;

}

Node* Copy(Node* root)

{

if (root == nullptr)

return nullptr;

Node* newnode = new Node(root->_key, root->_val);

newnode->_left = Copy(root->_left);

newnode->_right = Copy(root->_right);

return newnode;

}

//使用 后序遍历 释放

void Destroy(Node* root)

{

//空节点不需要释放，直接返回

if (root == nullptr)

return;

Destroy(root->_left);//递归释放左子树

Destroy(root->_right);//递归释放右子树

delete root;//释放根节点

}

void _InOrder(Node* root)

{

if (root == nullptr)

return;

_InOrder(root->_left);//遍历左子树

//打印信息

cout << root->_key << ":" << root->_val << endl;

_InOrder(root->_right);//遍历右子树

}

//直接遍历二叉树进行节点统计

size_t _Size(Node* root)

{

if (root == nullptr)

return 0;

//统计左子树节点个数

int left = _Size(root->_left);

//统计右子树节点个数

int right = _Size(root->_right);

return left + right + 1;//1是当前节点

}

};