一、二叉搜索树的概念
二叉搜索树又称为二叉排序树，它或者是一颗空树，或者是具有以下性质的二叉树：
- 若它的左子树不为空，则左子树上所有节点的值小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根结点的值
- 它的每一颗子树都是搜索二叉树，满足该三条规则。
可以简单的总结一下，整个左子树的值比根小，整个右子树的值比根大，且每一颗子树符合该规则
例如： 二叉搜索树 非二叉搜索树，3的左子树大于根
二、二叉搜索树的实现
二叉搜索树的实现，首先得创建一个节点类，用来存放数据，接着再创建树的框架，用来管理节点的插入，查找，删除等操作 。
2.1节点创建
实现成模板，可以存放各种类型的数据，为了让节点与节点之间关联起来，所以有两个指针，_left，_right分别指向左右节点 ,_data则是存放具体值。构造函数则是初始化节点的内容
template<class T>
struct BSTnode
{
BSTnode(const T& data = T())//初始化节点内容
:_left(nullptr)
, _right(nullptr)
, _data(data)
{}
BSTnode<T>* _left;
BSTnode<T>* _right;
T _data;
};2.2构造与拷贝构造
创建节点后，接着创建树，用来管理节点，首先就是实现构造函数对节点进行初识化，然后实现拷贝构造，拷贝构造需要将一颗树的所有节点值全拷贝过来，故可以采用递归的方式实现。
template<class T>
class BSTree
{
typedef BSTnode<T> Node;
typedef Node* PNode;
public:
BSTree()
:_Root(nullptr)
{}
BSTree(const BSTree<T>& t)
{
_Root = CopyNode(t._Root);
}
PNode CopyNode(PNode Root)
{
if (Root == nullptr)
{
return nullptr;
}
PNode node = new Node;//创建新结点,存放节点值
node->_data = Root->_data;//拷贝节点值
node->_left = CopyNode(Root->_left);//链接左节点
node->_right = CopyNode(Root->_right);//链接右节点
return node;
}
private:
PNode _Root;//采用节点指针
};
2.3插入(循环版本&&递归版本)
接下来进行具体的管理节点，首先就是节点的插入，思想的实现可以分为两个步骤：
1.树为空，则直接新增节点，赋值给_Root 指针
2.树不为空，按二叉树的性质搜索查找插入位置，插入新节点
3.若出现相同的值则不插入
二叉搜索树需要不断的进行比较，最终插入，所以其实现可以用循环和递归实现，为了表示是否插入成功，所以使其需要返回值。
例如：插入新节点，16、0。根据二叉搜索树的性质，进行比较，插入
循环版本
bool Insert(const T& data)
{
//空树,新增节点
if (_Root == nullptr)
{
_Root = new Node;
_Root->_data = data;
return true;
}
//不为空，进行比较
PNode cur = _Root;
PNode parent = nullptr;//存放cur的上一个位置
while (cur)
{
parent = cur;
if (data < cur->_data)//小于根节点，则往左子树
{
cur = cur->_left;
}
else if (data > cur->_data)//大于根节点，则往右子树
{
cur = cur->_right;
}
else//有相同值，返回假
{
return false;
}
}
//循环结束，说明找到了要插入的位置，但cur为空
//而parent是cur的上一个位置，所以用parent比较插入
if (data < parent->_data)
{
PNode node = new Node;
node->_data = data;
parent->_left = node;
}
else if (data > parent->_data)
{
PNode node = new Node;
node->_data = data;
parent->_right = node;
}
return true;
}递归版本
bool Insert(const T& data)
{
return _Insert(_Root,data);
}
bool _Insert(PNode& Root,const T& data)
{
//为空，新增节点，直接返回，或者，不为空在最后插入节点，返回
if (Root == nullptr)
{
//PNode node = new Node;
//Root = node;
//node->_data = data;
Root = new Node(data);
return true;
}
if (data < Root->_data)//小于根节点，往左子树
return _Insert(Root->_left, data);
else if (data > Root->_data)
return _Insert(Root->_right, data);//大于根节点，往右子树
else
return false;
}2.4查找(循环版本&&递归版本)
同理，查找需要不断进行比较，依然可以通过循化和递归实现。 查找成功，返回当前位置指针，否则返回nullptr
循环版本
PNode Find(const T& data)
{
//树空
if (_Root == nullptr)
{
return nullptr;
}
//不为空
PNode cur = _Root;
while (cur)
{
if (data < cur->_data)
{
cur = cur->_left;
}
else if (data > cur->_data)
{
cur = cur->_right;
}
else
{
return cur;//找到，返回该位置指针
}
}
return nullptr;
}
递归版本
PNode Find(const T& data)
{
return _Find(_Root,data);
}
PNode _Find(PNode Root,const T& data)
{
if (Root == nullptr)
{
return nullptr;
}
if (data < Root->_data)
{
return _Find(Root->_left, data);
}
else if (data > Root->_data)
{
return _Find(Root->_right, data);
}
else
{
return Root;
}
}
2.5删除(循环版本&&递归版本)
首先查找元素是否在二叉搜索树中，如果不存在，则返回，否则要删除的节点可能分下面四种情况：
1.要删除的结点无孩子结点
2.要删除的结点只有左孩子
3.要删除的结点只有右孩子
4.要删除的结点有左、右孩子结点
①要删除的节点无孩子、只有左孩子、右孩子可以归类为一种情况。 都是让删除节点的父亲指向删除节点的孩子即可。
②要删除的节点有左右孩子可以归类为一种情况。
删除该节点时，其还有左右孩子，所以导致的问题是得重新排序链接。为了保持二叉搜索树的结构，可以采用替换删除法：找一个替换我的节点，交换值，转换删除他。那么其有两种删除方式。
a.找删除结点的左子树的最大节点进行交换删除(左子树最右节点)
b.找删除结点的右子树的最小节点进行交换删除(右子树最左节点)
解释：因为左子树中的最大节点比删除结点的左孩子大、右孩子小。右子树中的最小节点也比删除结点的左孩子大、右孩子小。那么交换删除，依然满足二叉搜索树的结构。
在代码实现中，就采用第二种，找右子树的最小节点。
循环版本
bool Erase(const T& data)
{
if (_Root == nullptr)//树为空，返回fasle
return false;
PNode cur = _Root;
PNode parent = _Root;//跟踪cur,始终保持为cur的父亲
//查找要删除节点位置
while (cur)
{
if (data < cur->_data)
{
parent = cur;
cur = cur->_left;
}
else if (data > cur->_data)
{
parent = cur;
cur = cur->_right;
}
else
break;//找到跳出
}
//未找到，返回FALSE
if (cur == nullptr)
return false;
//要删除的节点只有右孩子
if (cur->_left == nullptr)
{
//要删除的节点是根节点，更新根节点，再删除
if (cur == _Root)
{
_Root = cur->_right;
}
//判断该删除结点是父亲的左孩子还是右孩子
if (data < parent->_data)//是父亲的左孩子
{
parent->_left = cur->_right;
}
else if(data > parent->_data)//是父亲的右孩子
{
parent->_right = cur->_right;
}
delete cur;
}
else if (cur->_right == nullptr)//要删除的结点只有左孩子
{
//要删除的节点是根节点，更新根节点，再删除
if (cur == _Root)
{
_Root = cur->_left;
}
//判断该删除结点是父亲的左孩子还是右孩子
if (data < parent->_data)//是父亲的左孩子
{
parent->_left = cur->_left;
}
else if(data > parent->_data)//是父亲的右孩子
{
parent->_right = cur->_left;
}
delete cur;
}
else//跟右子树的最左节点(即最小节点)进行交换，再删除
{
PNode pparent = cur;//跟踪parent
parent = cur->_right;//先指向右子树的根节点
//找右子树最左节点
while (parent->_left)
{
pparent = parent;
parent = parent->_left;
}
//交换，重新链接，删除
cur->_data = parent->_data;
if (cur == pparent)
{
pparent->_right = parent->_right;
}
else
{
pparent->_left = parent->_right;
}
delete parent;
}
return true;//删除成功，返回true
}
递归版本
bool Erase(const T& data)
{
return _Erase(_Root, data);
}
bool _Erase(PNode& Root,const T& data)//Root采用引用，引用的是上一个Root->_left。目的是，当找到删除结点，其只有一个孩子或者无孩子，就可以让删除结点的父亲指向孩子，该父亲就是当前Root，引用的是上一个Root->_left。即PNode& Root= Root->_left
{
if (Root == nullptr)
{
return false;
}
//查找删除结点
if (data < Root->_data)
{
_Erase(Root->_left, data);//小于查找节点，到左子树查找
}
else if (data > Root->_data)
{
_Erase(Root->_right, data);//大于查找节点，到右子树查找
}
else//找到删除结点，判断其是否有孩子，进行交换删除
{
PNode cur = Root;
//要删除的节点只有右孩子
if (Root->_left == nullptr)
{
Root = Root->_right;//链接右孩子
}
else if (Root->_right == nullptr)//要删除的节点只有左孩子
{
Root = Root->_left;//链接左孩子
}
else//要删除的节点有左右孩子，采用替换法删除
{
cur = Root->_right;
//寻找最左节点
while (cur->_left)
{
cur = cur->_left;
}
//交换
swap(Root->_data,cur->_data);
return _Erase(Root->_right, data);//转换成在删除结点的右子树中查找交换后要删除的节点，因为交换后的删除的节点其要么只有一个孩子要么没有孩子
}
delete cur;
cur = nullptr;
return true;
}
}2.6析构
void Delete(PNode Root)//后序递归删除
{
if (Root == nullptr)
return;
Delete(Root->_left);
Delete(Root->_right);
delete Root;
}
~BSTree()
{
if (_Root == nullptr)
delete _Root;
Delete(_Root);
}2.7总代码(循环版本&&递归版本)
循环版本：
//BSTeee-key.h
#include <iostream>
using namespace std;
namespace bit
{
template<class T>
struct BSTnode
{
BSTnode(const T& data = T())
:_left(nullptr)
, _right(nullptr)
, _data(data)
{}
BSTnode<T>* _left;
BSTnode<T>* _right;
T _data;
};
template<class T>
class BSTree
{
typedef BSTnode<T> Node;
typedef Node* PNode;
public:
BSTree()
:_Root(nullptr)
{}
BSTree(const BSTree<T>& t)
{
_Root = CopyNode(t._Root);
}
PNode CopyNode(PNode Root)
{
if (Root == nullptr)
{
return nullptr;
}
PNode node = new Node;
node->_data = Root->_data;
node->_left = CopyNode(Root->_left);
node->_right = CopyNode(Root->_right);
return node;
}
//插入
bool Insert(const T& data)
{
//空树
if (_Root == nullptr)
{
_Root = new Node;
_Root->_data = data;
return true;
}
//不为空
PNode cur = _Root;
PNode parent = nullptr;
while (cur)
{
parent = cur;
if (data < cur->_data)
{
cur = cur->_left;
}
else if (data > cur->_data)
{
cur = cur->_right;
}
else
{
return false;
}
}
if (data < parent->_data)
{
PNode node = new Node;
node->_data = data;
parent->_left = node;
}
else if (data > parent->_data)
{
PNode node = new Node;
node->_data = data;
parent->_right = node;
}
return true;
}
//查找
PNode Find(const T& data)
{
//树空
if (_Root == nullptr)
{
return nullptr;
}
//不为空
PNode cur = _Root;
while (cur)
{
if (data < cur->_data)
{
cur = cur->_left;
}
else if (data > cur->_data)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
//删除--替换删除法
bool Erase(const T& data)
{
if (_Root == nullptr)//树为空，返回fasle
return false;
PNode cur = _Root;
PNode parent = _Root;//跟踪cur,始终保持为cur的父亲
//查找要删除节点位置
while (cur)
{
if (data < cur->_data)
{
parent = cur;
cur = cur->_left;
}
else if (data > cur->_data)
{
parent = cur;
cur = cur->_right;
}
else
break;//找到跳出
}
//未找到，返回FALSE
if (cur == nullptr)
return false;
//要删除的节点只有右孩子
if (cur->_left == nullptr)
{
//要删除的节点是根节点，更新根节点，再删除
if (cur == _Root)
{
_Root = cur->_right;
}
//判断该删除结点是父亲的左孩子还是右孩子
if (data < parent->_data)//是父亲的左孩子
{
parent->_left = cur->_right;
}
else if(data > parent->_data)//是父亲的右孩子
{
parent->_right = cur->_right;
}
delete cur;
}
else if (cur->_right == nullptr)//要删除的结点只有左孩子
{
//要删除的节点是根节点，更新根节点，再删除
if (cur == _Root)
{
_Root = cur->_left;
}
//判断该删除结点是父亲的左孩子还是右孩子
if (data < parent->_data)//是父亲的左孩子
{
parent->_left = cur->_left;
}
else if(data > parent->_data)//是父亲的右孩子
{
parent->_right = cur->_left;
}
delete cur;
}
else//跟右子树的最左节点(即最小节点)进行交换，再删除
{
PNode pparent = cur;//跟踪parent
parent = cur->_right;//先指向右子树的根节点
//找右子树最左节点
while (parent->_left)
{
pparent = parent;
parent = parent->_left;
}
//交换，重新链接，删除
cur->_data = parent->_data;
if (cur == pparent)
{
pparent->_right = parent->_right;
}
else
{
pparent->_left = parent->_right;
}
delete parent;
}
return true;//删除成功，返回true
}
void Delete(PNode Root)
{
if (Root == nullptr)
return;
Delete(Root->_left);
Delete(Root->_right);
delete Root;
}
~BSTree()
{
if (_Root == nullptr)
delete _Root;
Delete(_Root);
}
void _InOrder(PNode Root)
{
if (Root == nullptr)
return;
_InOrder(Root->_left);
cout << Root->_data << " ";
_InOrder(Root->_right);
}
void InOrder()
{
_InOrder(_Root);
cout << endl;
}
private:
PNode _Root;//采用节点指针
};
void BSTreetest()
{
BSTree<int> t;
int a[] = { 8,3,1,10,6,4,7,14,13 };
for (int i = 0; i < 9; i++)
{
t.Insert(a[i]);
}
t.Erase(6);
BSTree<int> ts(t);
ts.InOrder();
}
}测试：
test.cpp
#include "BSTeee-key.h"
int main()
{
bit::BSTreetest();
return 0;
}输出结果：
递归版本：
//BSTeee-key2.h
#include <iostream>
using namespace std;
namespace bit
{
template<class T>
struct BSTnode
{
BSTnode(const T& data = T())
:_left(nullptr)
, _right(nullptr)
, _data(data)
{}
BSTnode<T>* _left;
BSTnode<T>* _right;
T _data;
};
template<class T>
class BSTree
{
typedef BSTnode<T> Node;
typedef Node* PNode;
public:
BSTree()
:_Root(nullptr)
{}
BSTree(const BSTree<T>& t)
{
_Root = CopyNode(t._Root);
}
PNode CopyNode(PNode Root)
{
if (Root == nullptr)
{
return nullptr;
}
PNode node = new Node;
node->_data = Root->_data;
node->_left = CopyNode(Root->_left);
node->_right = CopyNode(Root->_right);
return node;
}
//插入
bool Insert(const T& data)
{
return _Insert(_Root,data);
}
bool _Insert(PNode& Root,const T& data)
{
if (Root == nullptr)
{
PNode node = new Node;
Root = node;
node->_data = data;
return true;
}
if (data < Root->_data)
return _Insert(Root->_left, data);
else if (data > Root->_data)
return _Insert(Root->_right, data);
else
return false;
}
//查找
PNode Find(const T& data)
{
return _Find(_Root,data);
}
PNode _Find(PNode Root,const T& data)
{
if (Root == nullptr)
{
return nullptr;
}
if (data < Root->_data)
{
return _Find(Root->_left, data);
}
else if (data > Root->_data)
{
return _Find(Root->_right, data);
}
else
{
return Root;
}
}
//删除--替换删除法
bool Erase(const T& data)
{
return _Erase(_Root, data);
}
bool _Erase(PNode& Root,const T& data)
{
if (Root == nullptr)
{
return false;
}
if (data < Root->_data)
{
_Erase(Root->_left, data);
}
else if (data > Root->_data)
{
_Erase(Root->_right, data);
}
else
{
PNode cur = Root;
//要删除的节点只有右孩子
if (Root->_left == nullptr)
{
Root = Root->_right;//链接右孩子
}
else if (Root->_right == nullptr)//要删除的节点只有左孩子
{
Root = Root->_left;//链接左孩子
}
else//要删除的节点有左右孩子，采用替换法删除
{
cur = Root->_right;
//寻找最左节点
while (cur->_left)
{
cur = cur->_left;
}
//交换
swap(Root->_data, cur->_data);
return _Erase(Root->_right, data);//转换成在删除结点的右子树中查找交换后要删除的节点，因为交换后的删除的节点其要么只有一个孩子要么没有孩子
}
delete cur;
cur = nullptr;
return true;
}
}
void Delete(PNode Root)
{
if (Root == nullptr)
return;
Delete(Root->_left);
Delete(Root->_right);
delete Root;
}
~BSTree()
{
if (_Root == nullptr)
delete _Root;
Delete(_Root);
}
void _InOrder(PNode Root)
{
if (Root == nullptr)
return;
_InOrder(Root->_left);
cout << Root->_data << " ";
_InOrder(Root->_right);
}
void InOrder()
{
_InOrder(_Root);
cout << endl;
}
private:
PNode _Root;//采用节点指针
};
void BSTreetest()
{
BSTree<int> t;
int a[] = { 8,3,1,10,6,4,7,14,13 };
for (int i = 0; i < 9; i++)
{
t.Insert(a[i]);
}
BSTnode<int>* p = t.Find(5);
if (p == nullptr)
{
t.Insert(5);
}
t.Erase(3);
t.Erase(6);
BSTree<int> ts(t);
ts.InOrder();
}
}测试：
//test.cpp
#include "BSTeee-key2.h"
int main()
{
bit::BSTreetest();
return 0;
}输出结果：
三、二叉搜索树的应用
3.1 k模型 && kv模型
K模型：k模型即只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值。就跟上面的代码实现一样。
比如：查询某人是否买了机票。就可以建立采用搜索二叉树，在二叉搜索树中查询该人是否存在，存在，已买，否则，未买。
kv模型：每一个关键码key，都有与之对应的值value，即<key,value>的键值对。
比如：英汉词典就是英文与中文的对应关系，通过英文了以快速找到与其对应的中文，英文单词与其对应的中文(apple,"苹果")就构成一种键值对；
3.2 KV模型的实现
对于kv模型的实现没有什么太大变化，就是在加一个模板参数，在插入节点时，给另一个模板参数也进行赋值即可。进行比较时，还是按第一个参数来比较，即按key来比较，跟value无关。
//BSTree.h
#include <iostream>
#include <string>
using namespace std;
namespace bit
{
template<class K,class V>
struct BSTnode
{
BSTnode(const K& key = K(),const V& value= V())
:_left(nullptr)
, _right(nullptr)
, _key(key)
,_value(value)
{}
BSTnode<K, V>* _left;
BSTnode<K, V>* _right;
K _key;
V _value;
};
template<class K, class V>
class BSTree
{
public:
typedef BSTnode<K, V> Node;
typedef Node* PNode;
public:
BSTree()
:_Root(nullptr)
{}
//插入
bool Insert(const K& key, const V& value)
{
//空树
if (_Root == nullptr)
{
_Root = new Node;
_Root->_key = key;
_Root->_value = value;
return true;
}
//不为空
PNode cur = _Root;
PNode parent = nullptr;
while (cur)
{
parent = cur;
if (key < cur->_key)
{
cur = cur->_left;
}
else if (key > cur->_key)
{
cur = cur->_right;
}
else
{
return false;
}
}
if (key < parent->_key)
{
PNode node = new Node;
node->_key = key;
node->_value = value;
parent->_left = node;
}
else if (key > parent->_key)
{
PNode node = new Node;
node->_key = key;
node->_value = value;
node->_value = value;
parent->_right = node;
}
return true;
}
//查找
PNode Find(const K& key)
{
//树空
if (_Root == nullptr)
{
return nullptr;
}
//不为空
PNode cur = _Root;
while (cur)
{
if (key < cur->_key)
{
cur = cur->_left;
}
else if (key > cur->_key)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
//删除--替换删除法
bool Erase(const K& key)
{
if (_Root == nullptr)
return false;
PNode cur = _Root;
PNode parent = nullptr;
//查找要删除节点位置
while (cur)
{
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else
break;
}
//未找到，返回FALSE
if (cur == nullptr)
return false;
//要删除的节点只有右孩子
if (cur->_left == nullptr)
{
//要删除的节点是根节点，更新根节点，再删除
if (cur == _Root)
{
_Root = cur->_right;
}
//判断该删除结点是父亲的左孩子还是右孩子
if (key < parent->_key)//是父亲的左孩子
{
parent->_left = cur->_right;
delete cur;
}
else if(key > parent->_key)//是父亲的右孩子
{
parent->_right = cur->_right;
delete cur;
}
}
else if (cur->_right == nullptr)//要删除的节点只有右孩子
{
//要删除的节点是根节点，更新根节点，再删除
if (cur == _Root)
{
_Root = cur->_right;
}
//判断该删除结点是父亲的左孩子还是右孩子
if (key < parent->_key)//是父亲的左孩子
{
parent->_left = cur->_left;
delete cur;
}
else if(key > parent->_key)//是父亲的右孩子
{
parent->_right = cur->_left;
delete cur;
}
}
else//跟右子树的最左节点(即最小节点)进行交换，再删除
{
PNode pparent = cur;
parent = cur->_right;
//找最左节点
while (parent->_left)
{
pparent = parent;
parent = parent->_left;
}
//交换删除
cur->_key = parent->_key;
if (cur == pparent)
{
pparent->_right = parent->_right;
}
else
{
pparent->_left = parent->_right;
}
delete parent;
}
return true;
}
~BSTree()
{
if (_Root == nullptr)
delete _Root;
Delete(_Root);
}
void InOrder()
{
_InOrder(_Root);
cout << endl;
}
private:
void Delete(PNode Root)
{
if (Root == nullptr)
return;
Delete(Root->_left);
Delete(Root->_right);
delete Root;
}
void _InOrder(PNode Root)
{
if (Root == nullptr)
return;
_InOrder(Root->_left);
cout << Root->_key << ":" << Root->_value << endl;;
_InOrder(Root->_right);
}
PNode _Root;//采用节点指针
};
/*void BSTreetest()
{
BSTree<int> t;
t.Insert(1);
t.Insert(28);
t.Insert(3);
t.Insert(4);
t.InOrder();
}*/
//void BSTreetest2()
//{
// BSTree<int, int> t;
// t.Insert(1, 1);
// t.Insert(1, 1);
// t.Insert(2, 1);
// t.Insert(3, 1);
// t.Insert(4, 1);
// t.Insert(5, 1);
// t.Insert(6, 1);
// t.Erase(3);
// t.InOrder();
//}
//查询单词
//void BSTreetest3()
//{
// BSTree<string, string> dict;
// //插入单词
// dict.Insert("string", "字符串");
// dict.Insert("binary", "二叉");
// dict.Insert("search", "搜索");
// dict.Insert("tree", "树");
// dict.Insert("sort", "排序");
// //查询单词是否在
// string str;
// while (cin >> str)
// {
// BSTnode<string, string>* ret = dict.Find(str);
// if(ret == nullptr)
// {
// cout << "单词拼写错误，词库中没有这个单词:" << str << endl;
// }
// else
// {
// cout << str << "中文翻译:" << ret->_value << endl;
// }
// }
//}
//统计水果出现的次数
void BSTreetest4()
{
string str[] = { "香蕉","苹果","荔枝","梨","苹果", "苹果", "西瓜","香蕉","香蕉","梨" };
BSTree<string, int> countTree;
for (const auto& s : str)
{
BSTnode<string, int>* ret = countTree.Find(s);
if (ret == NULL)
{
countTree.Insert(s, 1);
}
else
{
ret->_value++;
}
}
countTree.InOrder();
}
}
测试：
//test.cpp
#include "BSTeee.h"
int main()
{
bit::BSTreetest4();
return 0;
}输出结果：
3.3二叉搜索树的性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个节点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是节点在二叉搜索树的深度的函数，即节点越深，则比较次数越多。
但对于同一个关键码的集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树),其平均比较次数为:log N
最差情况下，二叉搜索树退化为单支树，其平均比较次数为: N^2
所以问题就是，如果退化成单支树，二叉搜索树的性能就失去了。为了解决该问题，大佬们发明了了AVL树和红黑树，待后续章节进行学习。
end~
