🌈个人主页：秦jh_-CSDN博客

🔥 系列专栏：https://blog.csdn.net/qinjh_/category_12575764.html?spm=1001.2014.3001.5482

​ 

目录

前言

二叉搜索树

概念

操作 

查找 

插入 

中序遍历

​编辑​

 删除

 二叉搜索树的应用

性能分析

前言

💬 hello! 各位铁子们大家好哇。

             今日更新了二叉搜索树的相关内容

🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

二叉搜索树

概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树: 

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

​

操作 

查找 

从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。最多查找高度次，走到到空，还没找到，这个值不存在。 

插入 

树为空，则直接新增节点，赋值给root指针树不空，按二叉搜索树性质查找插入位置，插入新节点 。默认不能冗余，如果已经有相同的值了，就插入失败。

中序遍历

​

二叉搜索树的中序遍历，其实就是升序后的排序。因为根节点是私有的，这里不适合用友元。所以对于递归的函数，可以弄一个子函数为私有，套一层在外面，这里就不需要传形参了，不需要访问私有的根节点了。 

 删除

​ 

上图是我们即将使用的搜索二叉树模型。

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

要删除的结点无孩子结点（情况1） 要删除的结点只有左孩子结点（情况2） 要删除的结点只有右孩子结点（情况3）要删除的结点有左、右孩子结点（情况4）

实际上，情况1可以和2，3合并起来，不需要额外判断。

实际删除过程：

情况2：删除该节点且使该节点的父节点指向该节点的左孩子。情况3：删除该节点且使该节点的父节点指向该节点的右孩子。情况4：在它的右子树找最左节点进行交换，然后再处理该节点的删除问题。（或者找左子树的最右节点进行替换）

 删除的完整代码：

<code>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

{

//删除

//左为空，父亲指向我的右

if (cur->_left == nullptr)

{

if (cur == _root)

{

_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 (cur == _root)

{

_root = cur->_left;

}

else

{

//右为空，父亲指向我的左

if (cur == parent->_left)

{

parent->_left = cur->_left;

}

else

{

parent->_right = cur->_left;

}

}

delete cur;

}

else

{

//左右都不为空，替换法删除

//查找右子树的最左节点替代删除（也可找左子树的最右节点替换）

//注意删除根节点的特殊情况，此时rightmin的父亲为cur

Node* rightMinParent = cur;

Node* rightMin = cur->_right;

while (rightMin->_left)

{

rightMinParent = rightMin;

rightMin = rightMin->_left;

}

swap(cur->_key, rightMin->_key);

//判断rightmin在父亲的左边还是右边

//rightmin左边为空，所以rightmin的父亲指向rightmin的右边

if(rightMinParent->_left==rightMin)

rightMinParent->_left = rightMin->_right;

else

rightMinParent->_right = rightMin->_right;

delete rightMin;

}

return true;

}

}

return false;

}

​

注意，当删除全部节点时，需要更新根节点，如上图。

 二叉搜索树的应用

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

KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。

K模型代码：

<code>namespace key

{

template<class K>

struct BSTreeNode

{

BSTreeNode<K>* _left;

BSTreeNode<K>* _right;

K _key;

BSTreeNode(const K& key)

:_left(nullptr)

, _right(nullptr)

, _key(key)

{}

};

template<class K>

class BSTree

{

typedef BSTreeNode<K> Node;

public:

bool Insert(const K& key)

{

if (_root == nullptr)

{

_root = new Node(key);

return true;

}

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

{

return false;

}

}

cur = new Node(key);

if (parent->_key > key)

{

parent->_left = cur;

}

else

{

parent->_right = cur;

}

return true;

}

bool 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 true;

}

}

return false;

}

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

{

//删除

//左为空，父亲指向我的右

if (cur->_left == nullptr)

{

if (cur == _root)

{

_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 (cur == _root)

{

_root = cur->_left;

}

else

{

//右为空，父亲指向我的左

if (cur == parent->_left)

{

parent->_left = cur->_left;

}

else

{

parent->_right = cur->_left;

}

}

delete cur;

}

else

{

//左右都不为空，替换法删除

//查找右子树的最左节点替代删除（也可找左子树的最右节点替换）

Node* rightMinParent = cur;

Node* rightMin = cur->_right;

while (rightMin->_left)

{

rightMinParent = rightMin;

rightMin = rightMin->_left;

}

swap(cur->_key, rightMin->_key);

if (rightMinParent->_left == rightMin)

rightMinParent->_left = rightMin->_right;

else

rightMinParent->_right = rightMin->_right;

delete rightMin;

}

return true;

}

}

return false;

}

void InOrder()

{

_InOrder(_root);

cout << endl;

}

private:

void _InOrder(Node* root)

{

if (root == nullptr)

return;

_InOrder(root->_left);

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

_InOrder(root->_right);

}

private:

Node* _root = nullptr;

};

void BSTreeTest1()

{

int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };

BSTree<int> t1;

for (auto e : a)

{

t1.Insert(e);

}

t1.InOrder();

t1.Erase(8);

t1.InOrder();

for (auto e : a)

{

t1.Erase(e);

t1.InOrder();

}

}

}

KV模型代码：

namespace key_value

{

template<class K,class V>

struct BSTreeNode

{

BSTreeNode<K,V>* _left;

BSTreeNode<K,V>* _right;

K _key;

V _val;

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:

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

{

if (_root == nullptr)

{

_root = new Node(key,val);

return true;

}

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

{

return false;

}

}

cur = new Node(key,val);

if (parent->_key > key)

{

parent->_left = cur;

}

else

{

parent->_right = cur;

}

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;

}

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

{

//删除

//左为空，父亲指向我的右

if (cur->_left == nullptr)

{

if (cur == _root)

{

_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 (cur == _root)

{

_root = cur->_left;

}

else

{

//右为空，父亲指向我的左

if (cur == parent->_left)

{

parent->_left = cur->_left;

}

else

{

parent->_right = cur->_left;

}

}

delete cur;

}

else

{

//左右都不为空，替换法删除

//查找右子树的最左节点替代删除（也可找左子树的最右节点替换）

Node* rightMinParent = cur;

Node* rightMin = cur->_right;

while (rightMin->_left)

{

rightMinParent = rightMin;

rightMin = rightMin->_left;

}

swap(cur->_key, rightMin->_key);

if (rightMinParent->_left == rightMin)

rightMinParent->_left = rightMin->_right;

else

rightMinParent->_right = rightMin->_right;

delete rightMin;

}

return true;

}

}

return false;

}

void InOrder()

{

_InOrder(_root);

cout << endl;

}

private:

void _InOrder(Node* root)

{

if (root == nullptr)

return;

_InOrder(root->_left);

cout << root->_key << " ";

_InOrder(root->_right);

}

private:

Node* _root = nullptr;

};

void BSTreeTest2()

{

BSTree<string, string> dict;

dict.Insert("string", "字符串");

dict.Insert("left", "左边");

dict.Insert("insert", "插入");

string str;

while (cin >> str)

{

BSTreeNode<string, string>* ret = dict.Find(str);

if (ret)

{

cout << ret->_val << endl;

}

else

{

cout << "找不到" << endl;

}

}

}

}

KV模型只需要在K模型的基础上进行修改即可。

性能分析

​

根据二叉树结构的不同，时间复杂度也会不一样。

最优情况：二叉搜索树为完全二叉树(或者接近完全二叉树)，时间复杂度：O(logN)

最差情况：二叉搜索树退化为单支树(或者类似单支)，时间复杂度：O(N)