1.概念
二叉搜索树又称二叉排序树，可以是一棵空树，不为空具有以下性质:
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树
2.实现
2.1创建节点
2.2查找
创建cur来代替_root来循环遍历
1.从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
2.最多查找高度次，走到到空，还没找到，这个值不存在。
递归版本
在私有域中封装具体实现细节，在公共域中提供接口使用，作为成员函数在类中可直接访问私有成员变量。
递归的终止条件是1.找到空节点(失败) 2.找到key所在节点(成功)
若当前的key值小于目标key值，则递归地在当前节点的右树中查找；反之在左树查找。不断缩小搜索范围，直到找到目标key值或搜索范围为空。
2.3插入
bool Insert(const k& key)
{
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->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
创建cur来代替_root来循环遍历，提前保存父节点
1.树为空，则直接新增节点，赋值给root指针,插入成功
2.树不空，按二叉搜索树性质查找插入位置，插入新节点。若找到key值相同的节点就插入失败，因为二叉搜索树性质决定不允许有相同key值的节点同时存在。
3.找到空节点后创建新节点，注意记得用父节点链接上形成搜索二叉树，需要判断链接在父节点的左边还是右边。
递归版本
还是在私有域封装实现细节，公共域提供接口使用，作为类的成员函数可直接访问私有成员。
递归结束条件为找到空节点位置，创建新节点进行链接。
这里的神来之笔是Node*&root，每次递归下去的是当前节点指针的引用（），这样就可以省略提前保存父节点指针的步骤，直接进行链接即可。root永远是父亲右指针和左指针的别名，这样就不用判断重新链接在父指针的左还是右。为什么循环不能传指针的引用？
引用的问题是不能改变指针指向，循环中没办法使用，递归可以因为每次都会创建新的栈帧，不同域中可以定义同名变量，每个栈帧中的引用都不同，每次递归都创建新的引用
2.4删除
删除时有三种情况：
1.删除节点没有孩子
2.删除节点只有一个孩子
3.有两个孩子
解决办法：
a：1和2属于直接删除场景，删除后父节点重新链接即可(nullptr或子节点)
b：3用替换法，用左子树的最大节点(最右节点)，或者右子树的最小节点(最左节点)。这样能确保交换根节点和要删除节点的key值后左子树key值依然小于根节点key值，右子树key值依然大于根节点key值，满足二叉搜索树性质。最后删除 要删除节点位置即可。
bool Erase(const k& key)
{
Node* cur = _root;
Node* parent = cur;
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 (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
}
//删除节点的右树为空
else if (cur->_right == nullptr)
{
//处理跟=根节点为要删除节点情况
if (cur == _root)
{
_root = cur->_left;
}
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
//要删除节点有两个孩子情况
else
{
//找替代节点,以左边为例
Node* parent = cur;
Node* leftmax = cur->_left;
while (leftmax->_right)
{
parent = leftmax;
leftmax = leftmax->_right;
}
swap(cur->_key, leftmax->_key);
//删除后链接
if (parent->_right == leftmax)
{
parent->_right = leftmax->_left;
}
if (parent->_left == leftmax)
{
parent->_left = leftmax->_left;
}
cur = leftmax;
}
delete cur;
return true;
}
}
return false;
}
代码逻辑：
1.创建cur来代替_root来循环遍历，提前保存父节点
2.找要删除节点的位置，比较当前位置key值与目标key值，不断更新父节点位置和cur节点位置，循环遍历下去，直到找到目标位置
3.依次分析删除的三种情况，注意检查删除节点是根节点的情况
需要将根节点更新到子树不为空的位置，这样父节点也跟着更新了(Node* parent = cur)，若不更新父节点为空，会造成非法访问的问题
4.重点分析删除节点有两个孩子情况：
左边和右边情况分别创建leftmax或rightmax来记录替代节点，父节点赋值为cur，可以避免父节点为空跳过循环中父节点赋值而造成的非法访问问题。找到后交换两节点中key值，再进行删除后的重新链接
递归版本
public:
bool EraseR(const k& key)
{
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* leftmax = root->_left;
while (leftmax->_right)
{
leftmax = leftmax->_right;
}
swap(leftmax->_key, root->_key);
return _EraseR(root->_left, key);
}
delete del;
return true;
}
}
递归终止条件1.根节点为空返回false 2.删除成功返回true
代码逻辑：
1.递归查找要删除的节点
2.当前key值等于目标key值，进行删除逻辑：
保存要删除节点到临时指针del
然后重新链接树，左子树为空，将当前节点右子树链接到父节点；右子树为空，将当前节点左子树链接到父节点；左右子树都不为空时，找到左子树的最大节点(最右节点)，或右子树的最小节点(最左节点)，将该节点key值与根节点key值交换，然后递归的在根节点的左子树中删除目标key值，这样目标key值所在节点从有两个孩子变成没有孩子辨析：
return _EraseR(root->_left, key);第一个参数若用leftmax
删除接口传参Node*& root，用的指针的引用，传下来的是节点指针的引用，所以不需要提前保存父节点进行重新链接。但此处传leftmax指针的引用实际上是指向1节点指针的引用(当前节点指针的引用)，将3这个节点删除后8节点指针指向没有改变，导致结构混乱。应该传root->_left，指向3节点，发现3的右节点为空直接指向1节点，正确完成删除
感受指针引用的妙处
以右子树为空的情况分析：正常情况下，root是父亲右指针或左指针的别名，直接更改父节点指向，上文已分析过
当要删除节点为空节点时，此时root为_root的别名,同样可以直接更改_root的指向
2.5复制
拷贝构造函数使用参数 t 来获取原对象的数据，然后根据这些数据构造一个新对象，新对象在内存中是完全独立的副本。复用copy函数实现深拷贝
递归终止条件1.传入节点为空无需复制返回空指针 2.每次递归调用中创建一个key值与原树相同的节点
通过后序遍历递归复制左子树和右子树，在递归过程中创建节点，在返回过程中链接形成树型结构
2.6销毁
采用后序遍历的方式销毁二叉树，释放当前节点占用内存后，记得将root指针置空
析构函数复用销毁的实现
3.二叉搜索树的应用
key搜索模型：
K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。上述代码实现就是该模型的应用
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
key_value模型：
每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对
比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；
再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对
namespace key_value
{
template<class k, class v >
struct BSTreeNode
{
BSTreeNode<k,v>* _left;
BSTreeNode<k,v>* _right;
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:
BSTree()
:_root(nullptr)
{
}
//封装一次可以通过类直接调用
void _Inorder()
{
Inorder(_root);
cout << endl;
}
Node* FindR(const k& key)
{
return _FindR(_root, key);
}
bool InsertR(const k& key,const v&value)
{
return _InsertR(_root, key,value);
}
bool EraseR(const k& key)
{
return _EraseR(_root, key);
}
private:
void Inorder(Node* _root)
{
if (_root == nullptr)
{
return;
}
Inorder(_root->_left);
cout << _root->_key << ":"<<_root->_value<<endl;
Inorder(_root->_right);
}
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* leftmax = root->_left;
while (leftmax->_right)
{
leftmax = leftmax->_right;
}
swap(leftmax->_key, root->_key);
return _EraseR(root->_left, 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;
}
}
Node* _root;
};
}
实现思路与key模型基本相同，只是节点中多增加了_value成员变量，BSTree类中多增加了一个模板参数v，实现插入功能时要同时插入value值。
- 测试代码
void testBSTree1()
{
key_value::BSTree<string, string> dict;
dict.InsertR("mint", "薄荷");
dict.InsertR("forever", "永远");
dict.InsertR("love", "相爱");
string str;
while (cin >> str)
{
key_value::BSTreeNode<string, string>* ret = dict.FindR(str);
if (ret)
{
cout << ret->_value << endl;
}
else
{
cout << "无此单词" << endl;
}
}
}
输入CTRLz+换行结束输入，正常退出ctrlc直接关掉程序
性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
1.理想情况下，树为完全平衡的二叉树，高度为 O(log 2 N)，此时增删查改操作的时间复杂度均为 O(logN)
2.若数据是有序或接近有序的，树可能会退化成链表，性能急剧下降，此时时间复杂度为 O(N)
