二叉搜索树

定义

二叉搜索树又称二叉排序树，它可能是一棵空树，也可能是具有以下性质的二叉树:
1.若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

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

那么也可得知每个结点的value在树中都是唯一的！即不存在相同的的值

如下图

实现

节点

template<typename T>
struct Bstree_Node
{
 Bstree_Node<T>* _left;
 Bstree_Node<T>* _right;
T _key;
Bstree_Node(const T& key)
:_key(key)
,_left(nullptr)
,_right(nullptr)
{}
};
1
2
3
4
5
6
7
8
9
10
11
12

类的框架

template<typename T>
class BSTree
{
typedef Bstree_Node<T> node;//重定义一下节点的名字
public:
//成员函数的实现
bool insert(const T& key)
{}
bool erase(const T& key)
{}
//......
private:
node* _root=nullptr;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

insert函数

bool insert(const T& key)
{
if (_root == nullptr)//如果根节点为空，则new个节点给根
{
_root = new node(key);
return true;
}
node* parent = nullptr;//记录根父节点
node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;//找到与新插入的点的值相同的子节点-直接false
}
}
//找到空结点
cur = new node(key);
if (cur->_key > parent->_key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

find函数

bool find(const T& key)
{
node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
cur = cur->_right;
}
else if (key < cur->_key)
{
cur = cur->_left;
}
else if (key == cur->_key)
{
return true;
}
}
return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

erase函数-方法一

找到要删除的节点时，此时该节点为根，把根的左子树链接到根的右子树的最左边最下面的左节点的左节点【此左节点的左孩子为空】上。 （该左节点为 根的右子树的最小值，与根的左孩子最接近）

动图展示的是删除的点是parent节点的左节点（parent节点为要删除节点的父节点），删除的点是parent节点的右节点也是如此

看图可能有点蒙，结合代码来看

//当根是要删除的节点，根的左右孩子都不为空时
node* right = cur->_right;
while (right->_left)
{
right = right->_left;
}
right->_left = cur->_left;
if (parent->_left == cur)
{
parent->_left = right;
delete cur;
return true;
}
else
{
parent->_right = right;
delete cur;
return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

整个erase函数代码

bool erase(const T& key)
{
node* parent = nullptr;
node* cur = _root;
if (_root == nullptr)
{
return false;
}
if (_root->_key == key)//删除根节点时
{
//左右空
if (cur->_left == nullptr && cur->_right == nullptr)
{
_root = nullptr;
return true;
}
//左空
else if (cur->_left == nullptr)
{
_root =_root->_right;
return true;
}
//右空
else if (cur->_right == nullptr)
{
_root = _root->_left;
return true;
}
//左右都不空
else
{
node* right = cur->_right;
while (right->_left)
{
right = right->_left;
}
right->_left = cur->_left;
_root = right;
return true;
}
}

while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else//找到了
{//左右节点都为空
if (cur->_left == nullptr && cur->_right == nullptr)
{
if (parent->_left == cur)
{
delete cur;
parent->_left = nullptr;
return true;
}
else
{
delete cur;
parent->_right = nullptr;
return true;
}
}

//左节点为空
else if (cur->_left == nullptr)
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
delete cur;
return true;
}
else
{
parent->_right = cur->_right;
delete cur;
return true;
}
}
//右节点为空
else if (cur->_right == nullptr)
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
delete cur;
return true;
}
else
{
parent->_right = cur->_left;
delete cur;
return true;
}
}
//左右节点都不为空
else
{
node* right = cur->_right;
while (right->_left)
{
right = right->_left;
}
right->_left = cur->_left;
if (parent->_left == cur)
{
parent->_left = right;
delete cur;
return true;
}
else
{
parent->_right = right;
delete cur;
return true;
}
}
}
}
return false;
//找到空结点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

erase函数-方法二

把要删除的节点(cur)的值和要删除的节点(cur)的右子树的最左边最底下的左节点(right)的值【该节点的左孩子为空】交换（或者赋值给cur节点），然后把该左节点(right)的右孩子链接到该左节点的父节点(parent)的左边，最后删除该左节点即可。

   node* parent = cur;
   node* right = cur->_right;
while (right->_left)
 {
parent = right;
right = right->_left;
  }
       cur->_key = right->_key;//交换值
   if (right == parent->_left)//左
{
parent->_left = right->_right;
}
    else
{
parent->_right = right->_right;
}
delete right;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

整体函数代码如下

bool erase(const T& key)
{
node* parent = nullptr;
node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else
//找到了
{
//1.左为空
//2.右为空
//3.左右都不为空
if (cur->_left == nullptr)
{
if (cur == _root)//要删的节点为根节点
{
_root = _root->_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 = _root->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
else
//两边都不为空
{
node* parent = cur;
node* right = cur->_right;
while (right->_left)
{
parent = right;
right = right->_left;
}
cur->_key = right->_key;//交换值
if (right == parent->_left)//左
{
parent->_left = right->_right;
}
else
{
parent->_right = right->_right;
}
delete right;
}
return true;
}
}
return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

递归实现

_insert_R函数

通过引用，把新建的节点直接赋于给已经链接好的空节点。

bool _insert_R(node*& root, const T& key)
{
if (root == nullptr)//走到空--即找到位置存放含key的节点
{
root = new node(key);//因为用的是引用，此时这个空节点就是父节点的子节点别名，相当于new了一个新的子节点，此时已经链接上了父节点
return true;
}
if (root->_key < key)
{
return (_insert_R(root->_right, key));
}
else if (root->_key > key)
{
return (_insert_R(root->_left, key));
}
else
{
return false;//遇到与key相同的节点，返回false
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

_erase_R函数

这里也是通过引用，具体看下面的动图

bool _erase_R(node*& root, const T& key)//递归实现erase函数
{
if (root == nullptr)//没找到或者直接传了一个空节点进来
{
return false;
}

if (root->_key > key)
{
return _erase_R(root->_left, key);
}
else if (root->_key < key)
{
return _erase_R(root->_right, 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;
}
//minright为右子树最左最底下子节点
swap(root->_key, minright->_key);//跟要删除的节点交换
//转换到右子树去删除节点，此时要删除的节点的左子树为空，到该节点时，要该节点的右节点代替要删除的节点
 return  _erase_R(root->_right, key);
}
delete del;
return true;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

构造函数

BSTree()//构造函数
:_root(nullptr)
{}
1
2
3

析构函数

~BSTree()//析构函数
{
Destory(_root);
_root = nullptr;
}
1
2
3
4
5

Destory函数

void Destory(node*root)//后序遍历删除节点
{
if (root == nullptr)
return;
Destory(root->_left);
Destory(root->_right);
delete root;
}
1
2
3
4
5
6
7
8

拷贝构造

BSTree(const BSTree<T>& t)//拷贝构造
{
_root = Copy(t._root);//赋值重载
}
1
2
3
4

Copy函数

前序遍历构建树

node* Copy(node* root)
 {
if (root == nullptr)
return nullptr;
node* Newroot = new node(root->_key);
Newroot->_left = Copy(root->_left);
Newroot->_right = Copy(root->_right);
return Newroot;
}
1
2
3
4
5
6
7
8
9

赋值重载

这里由于传过来的参数为形参，所以得先走拷贝构造函数拷贝构造一份参数，然后再走赋值重载

BSTree<T>&operator= ( BSTree<T> t)//赋值重载
{
swap(t._root, _root);
return *this;
}
1
2
3
4
5

K模型和KV模型

K模型

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

比如上面实现的二叉搜索树就是K模型，往里面插入(insert)单词，之后查找(find)，就能知道有木有这个单词。

KV模型

每一个关键码key都有与之对应的value，即为<Key,Value>的键值对。这个模型在生活中非常常见。

比如大学生有没有逃课，(缺课在教务系统中有记录)，那么这里的KV模型为<stdent ID,count>，前者关键码为学生的学号，后者为缺课次数。那么在教务系统中只需搜索学生卡号，就能知道你缺课了几次。

下面简单的实现了搜索函数、插入函数和打印函数

namespace KV {
template<typename K,typename V>
struct Bstree_Node
{
Bstree_Node<K,V>* _left;
Bstree_Node<K,V>* _right;
K _key;
V _value;
Bstree_Node(const K& key,const V& value)
:_key(key)
,_value(value)
, _left(nullptr)
, _right(nullptr)
{}
};
template<typename K,typename V >
class BSTree
{
typedef Bstree_Node<K,V> node;
public:

void Inorder()//中序遍历打印---左中右
{
_Inorder(_root);
cout << endl;
}

node* _find(const K& key)
{
node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
cur = cur->_right;
}
else if (key < cur->_key)
{
cur = cur->_left;
}
else if (key == cur->_key)
{
return cur;
}
}
return 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;
}

void _Inorder(node* root)
{
if (root == nullptr)
{
return;
}
_Inorder(root->_left);
cout << " " << root->_key << " " << root->_value << endl;
_Inorder(root->_right);

}
private:
node* _root = nullptr;
};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

现在这里只需要输入关键字key（名字）即可知道学生对应的缺课次数

简单介绍DFS和BFS

DFS即Depth First Search —深度优先遍历，是针对图和树的遍历算法。如最大路径问题。一般使用堆或栈来辅助实现DFS算法。其主要过程简化概要为对每一个可能的分支路径深入到不能在深入为止，即遇到死胡同再回退，回退过程中遇到没搜索过的支路，就进入该支路进行搜索，每个节点只能访问一次。比如前序遍历

BFS即Breadth First Search—广度优先遍历。这是连通图的一种遍历算法，也是很多重要的图的模型。即为从一个点（根）开始，彻底遍历搜索图（树）的所有节点。一般用队列来辅助实现BFS算法。比如层序遍历

下面是二叉搜索树，简易的模拟一下DFS（前序遍历）和BFS（层序遍历）

二叉搜索树的性能分析

由于插入和删除操作都必须先查找，查找效率直接决定了二叉搜索树中各个功能的性能。

对于有n个节点的二叉搜索树，若每个元素查找的概率相等，那么平均查找长度就在于树的深度了，即结点越深，查找的次数就越多。

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

若二叉搜索树像是下图这样的结构，即最优情况：二叉搜索树为完全二叉树或者接近完全二叉树，其平均查找次数为
$$lo{g}_{2}N$$

但如果像是这样的单支树或者类似单支树，其平均查找次数为
$$N/2$$
这时候二叉搜索树退化为单支树，其二叉搜索树的性能就失去了，那能否进行改进呢？怎么改进使得不论以什么次序插入关键码时，二叉搜索树的性能都能达到最优呢？后续在AVL树和红黑树的更新中会提到，敬请期待~

对二叉搜索树的介绍就到这了，感谢宁的支持