二叉搜索树
- 1.二叉搜索树概念
- 2.二叉搜索的实现
- 2.1结点
- 2.1基本框架
- 2.2插入
- 2.3查找
- 2.4删除
- 2.5打印
- 3.二叉搜索树递归实现
- 3.1查找
- 3.2插入
- 3.3删除
- 4.二叉搜索树默认成员函数
- 4.1构造
- 4.2析构
- 4.3拷贝构造
- 4.4赋值重载
- 6.二叉搜索树的应用
- 6.1K模型
- 6.2KV模型
- 7.二叉搜索树的性能分析
喜欢的点赞，收藏，关注一下把！
1.二叉搜索树概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3. 它的左右子树也分别为二叉搜索树
注意二查搜索树是一个单值树。 如下图：
2.二叉搜索的实现
2.1结点
template<class K>
struct BSTreeNode
{
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
BSTreeNode(const K& key)
:_key(key)
,_left(nullptr)
,_right(nullptr)
{}
};
2.1基本框架
template<class T>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
//构造等。。
bool Insert(const K& key)
{}
bool Erase(const K& key)
{}
bool Find(const K& key)
{}
private:
//先不写构造
Node* _root=nullptr;
};
二叉搜索树，没有提供改的成员函数。更准确来说二叉搜索树K模型不能去任意修改key值，可能会破坏二叉搜索树的结构。KV模型可以修改值这个我们下面说。
2.2插入
二叉搜索树的插入不像是普通二叉树插入那样，插入结点之后还需要保持二叉搜索树的形状。因此我们需要先找到要插入结点的位置，然后再插入。
bool Insert(const K& key)
{
//树为空
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
//寻址
Node* cur = _root;
while (cur)
{
if (_root->_key < key)
cur = cur->_right;
else if (_root->_key > key)
cur = cur->_left;
else //相等
return false;
}
//插入
cur = new Node(key);
return true;
}
我这样插入，有没有什么问题？
我们需要一个parent的指针，指向它的父亲结点，然后把9插入到父亲结点指针里，这样才能真正插入到树里。
但是这样写需要注意的是需要知道是插入父亲的左指针，还是右指针。
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
//往下走之前，记录一下父亲
parent = cur;
if (cur->_key < key)
cur = cur->_right;
else if (cur->_key > key)
cur = cur->_left;
else
return false;
}
cur = new Node(key);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
2.3查找
bool Find(const K& key)
{
if (_root == nullptr)
return false;
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;
}
2.4删除
删除是二叉搜索树中最难的，情况很多，都需要考虑到。
-
删7（叶子结点），可以直接删除，但是直接删除7，父亲结点右指针就野指针了。因此我们需要把父亲结点指针置为空。指向7左孩子还是右孩子都可以。
-
删14（只有一个左孩子，右为空），需要找到14的父亲结点，然后让父亲结点右指针指向14的左孩子结点。
-
那还有一种情况肯定是只有一个右孩子，左为空，让父亲指针指向这个右孩子。
其实上面三种情况，可以总结成两种情况。
1. 左孩子为空
2. 右孩子为空
叶子结点，让父亲指向左孩子右孩子都可以。
左为空，父亲指针指向右孩子，右为空，父亲指针指向左孩子。
bool Erase(const K& key)
{
if (_root == nullptr)
return false;
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
{
//1.左为空
if (cur->_left == nullptr)
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else if (parent->_right == cur)
{
parent->_right = cur->_right;
}
delete cur;
}
//2.右为空
else if (cur->_right == nullptr)
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else if (parent->_right == cur)
{
parent->_right = cur->_left;
}
delete cur;
}
//3.左右都不为空
else
{
}
return true;
}
}
return false;
}
先看前左为空，和右为空两种情况，请问有没有上面bug？
如果要被删除的是根节点呢？当前代码行不行？
是不是要报野指针的错误，根本没有parent指针。
那该如何解决呢？
是不是让根结点往下走一步就行了。
bool Erase(const K& key)
{
if (_root == nullptr)
return false;
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
{
//1.左为空
if (cur->_left == nullptr)
{
//被删结点是根结点
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else if (parent->_right == cur)
{
parent->_right = cur->_right;
}
}
delete cur;
}
//2.右为空
else if (cur->_right == nullptr)
{
//被删结点是根结点
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else if (parent->_right == cur)
{
parent->_right = cur->_left;
}
}
delete cur;
}
//3.左右都不为空
else
{
}
return true;
}
}
return false;
}
3.左右都不为空
删3，左右都不为空，具体做法如下：
方法1：找左子树最大结点替换删除
将左边最大孩子1，赋值给3，把删3转换成删1。
方法2：找右子树最小结点替换删除
左边最大----->左孩子最右结点
右边左小----->右孩子最左结点
//3.左右都不为空
else
{
//1.右孩子最小
Node* Minright = cur->_right;
Node* parent = nullptr;
while (Minright->_left)
{
parent = Minright;
Minright = Minright->_left;
}
parent->_left = Minright->_right;
delete Minright;
}
上面代码有没有上面问题？
对于删除3没有问题。那删除8呢？
10就是右边最小结点，不需要再往下找了。
循环进不去，parent又会带来野指针得问题。该怎么解决？
所以parent初始值不能置为空，设置为cur最好，并且parent的指针也不能那样随意指向，需要判断，Minright是parent的左孩子还是右孩子。
//3.左右都不为空
else
{
//1.右孩子最小
Node* Minright = cur->_right;
Node* parent = cur;
while (Minright->_left)
{
parent = Minright;
Minright = Minright->_left;
}
if (parent->_left == Minright)
{
parent->_left = Minright->_right;
}
else
{
parent->_right == Minright->_right;
}
delete Minright;
}
完整代码
bool Erase(const K& key)
{
if (_root == nullptr)
return false;
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
{
//1.左为空
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else if (parent->_right == cur)
{
parent->_right = cur->_right;
}
}
delete cur;
}
//2.右为空
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else if (parent->_right == cur)
{
parent->_right = cur->_left;
}
}
delete cur;
}
//3.左右都不为空
else
{
//1.右孩子最小
Node* Minright = cur->_right;
Node* parent = cur;
while (Minright->_left)
{
parent = Minright;
Minright = Minright->_left;
}
cur->_key=Minright->_key;
if (parent->_left == Minright)
{
parent->_left = Minright->_right;
}
else
{
parent->_right = Minright->_right;
}
delete Minright;
}
return true;
}
}
return false;
}
如果想替换成左孩子最大，代码完全类似。
//3.左右都不为空
else
{
//2.左孩子最大
Node* Maxleft = cur->_left;
Node* parent = cur;
while (Maxleft->_right)
{
parent = Maxleft;
Maxleft = Maxleft->_right;
}
cur->_key = Maxleft->_key;
if (parent->_left == Maxleft)
{
parent->_left = Maxleft->_left;
}
else
{
parent->_right = Maxleft->_left;
}
delete Maxleft;
}
2.5打印
二叉搜索树中序是一个递增序列。
中序遍历代码很简单。但是注意我们这是在类里面的中序遍历。
void InOrder(Node* root)
{
if (root == nullptr)
return;
InOrder(root->_left);
cout << root->_key < " ";
InOrder(root->_right);
}
中序需要把_root传就去，但是_root是一个私有成员变量不能访问。
在类里面写递归函数都会遇到这样的问题。
1.写一个Getroot的函数
2.套一层，写个子函数
void InOrder()
{
_InOrder(_root);
cout<<endl;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
3.二叉搜索树递归实现
递归代码量少，但是理解起来比较困难。一般建议有循环先写循环，然后再考虑写递归。
对于二叉树的递归，我们要有分治的思想，先处理根结点这棵树，然后再左子树右子树，因为左子树和右子树的处理方法和根结点这个树是一样的。
其实二叉搜索树的递归都是一个思想，空要怎么处理，比根大递归往右，比根小递归往左。
3.1查找
bool FindR(const K& key)
{
return _FindR(_root, key);
}
private:
bool _FindR(Node* root, const K& key)
{
if (root == nullptr)
return false;
if (root->_key < key)
return _FindR(root->_right, key);
else if (root->_key > key)
return _Findr(root->_left, key);
else
return true;
}
3.2插入
如果为空就申请结点插入，比根大往右，比根小往左，和根相等插入失败。
bool _InsertR(Node* root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_key < key)
return _InsertR(root->_right, key);
else if (root->_key > key)
return _InsertR(root->_left,key);
else
return false;
}
这个代码还不完整，有问题。
假如插入为空的时候，插入8，再插入3。
插入3的时候，根本没有插上。
这里只修改一处地方就成了。
//给指针加个别名
bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_key < key)
return _InsertR(root->_right, key);
else if (root->_key > key)
return _InsertR(root->_left,_key);
else
return false;
}
root虽然指向你，但是同时又是父亲的左指针或右指针的别名
3.3删除
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 _Erase(root->_left, key);
}
else
{
//1.左为空
//2.右为空
//3.左右都为空
if (root->_left == nullptr)
{
}
else if (root->_right == nullptr)
{
}
else
{
}
return true;
}
}
这里还需要再去申请一个parent吗？还需要知道7是父亲的左孩子还是右孩子吗？
显然是不用的，刚才说过，root虽然指向你，但是同时又是父亲的左指针或右指针的别名
root是父亲(6)的右指针的别名。这里就已经知道7是父亲的右指针了。并且也不用担心父亲为空的情况。
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
{
//1.左为空
//2.右为空
//3.左右都为空
Node* cur = root;//注意不能直接删除root，因为下面root已经改变了，所以必须保存要被删除的结点
if (root->_left == nullptr)
{
root = root->_right;
}
else if (root->_right == nullptr)
{
root = root->_left;
}
else
{
}
delete cur;
return true;
}
}
左右都不为空，可以向非递归那样删除。也可以交换删除。
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
{
//1.左为空
//2.右为空
//3.左右都为空
Node* cur = 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;
}
swap(root->_key, Minright->_key);
return _EraseR(root->_right, key);
}
delete cur;
return true;
}
}
非递归删除
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
{
//1.左为空
//2.右为空
//3.左右都为空
Node* cur = root;
if (root->_left == nullptr)
{
root = root->_right;
}
else if (root->_right == nullptr)
{
root = root->_left;
}
else
{
Node* Minright = root->_right;
Node* parent = root;
while (Minright->_left)
{
parent = Minright;
Minright = Minright->_left;
}
root->_key = Minright->_key;
if (Minright == parent->_left)
{
parent->_left = Minright->_right;
}
else
{
parent->_right = Minright->_right;
}
delete Minright;
return true;
}
delete cur;
return true;
}
}
4.二叉搜索树默认成员函数
4.1构造
//构造
BSTree()
:_root(nullptr)
{}
4.2析构
删除二叉树一般采用后序递归删除。
~BSTree()
{
Delete(_root);
}
private:
void Delete(Node* root)
{
if (root == nullptr)
return;
Delete(root->_left);
Delete(root->_right);
delete root;
}
4.3拷贝构造
构建一个二叉树一般建议前序递归创建
BSTree(const BSTree<K>& t)
{
_root = Copy(t._root);
}
private:
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* newnode = new Node(root->_key);
newnode->_left = Copy(root->_left);
newnode->_right = Copy(root->_right);
return newnode;
}
4.4赋值重载
传统写法
BSTree<K>& operator=(const BSTree<K>& t)
{
if (this != &t)
{
Delete(_root);
_root = Copy(t._root);
}
return *this;
}
现代写法，复用拷贝构造函数
//现代写法
BSTree<K>& operator=(BSTree<K> t)
{
swap(_root, t._root);
return *this;
}
6.二叉搜索树的应用
6.1K模型
K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
K模型不允许插入相同的key值，也不允许修改key，否则可能破坏K模型的结构。
假设让写一段程序，用来检测英语作家，写作内容是否拼写错误。
这时可以采用K模型。
- 把词库中的单词作为Key，构建一颗搜索二叉树
- 在二叉搜索树中检索每个单词是否在这个树中，不再就报错。
Key的搜索模型------>判断在不在？
6.2KV模型
KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。
通过Key查找或修改Value。 K模型不允许修改，KV模型允许修改。
KV模型就是增加了一个V类型。Find成员函数的返回值需要修改一下。
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)
:_key(key)
,_value(value)
, _left(nullptr)
, _right(nullptr)
{}
};
template<class K,class V>
class BSTree
{
typedef BSTreeNode<K,V> Node;
public:
//构造
BSTree()
:_root(nullptr)
{}
BSTree(const BSTree<K,V>& t)
{
_root = Copy(t._root);
}
//现代写法
BSTree<K,V>& operator=(BSTree<K,V> t)
{
swap(_root, t._root);
return *this;
}
~BSTree()
{
Delete(_root);
_root = 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)
{
//往下走之前，记录一下父亲
parent = cur;
if (cur->_key < key)
cur = cur->_right;
else if (cur->_key > key)
cur = cur->_left;
else
return false;
}
cur = new Node(key,value);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
bool Erase(const K& key)
{
if (_root == nullptr)
return false;
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
{
//1.左为空
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else if (parent->_right == cur)
{
parent->_right = cur->_right;
}
}
delete cur;
}
//2.右为空
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else if (parent->_right == cur)
{
parent->_right = cur->_left;
}
}
delete cur;
}
//3.左右都不为空
else
{
//1.右孩子最小
/*Node* Minright = cur->_right;
Node* parent = cur;
while (Minright->_left)
{
parent = Minright;
Minright = Minright->_left;
}
if (parent->_left == Minright)
{
parent->_left = Minright->_right;
}
else
{
parent->_right = Minright->_right;
}
delete Minright;*/
//2.左孩子最大
Node* Maxleft = cur->_left;
Node* parent = cur;
while (Maxleft->_right)
{
parent = Maxleft;
Maxleft = Maxleft->_right;
}
cur->_key = Maxleft->_key;
if (parent->_left == Maxleft)
{
parent->_left = Maxleft->_left;
}
else
{
parent->_right = Maxleft->_left;
}
delete Maxleft;
}
return true;
}
}
return false;
}
Node* Find(const K& key)
{
if (_root == nullptr)
return nullptr;
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;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* newnode = new Node(root->_key,root->_value);
newnode->_left = Copy(root->_left);
newnode->_right = Copy(root->_right);
return newnode;
}
void Delete(Node* root)
{
if (root == nullptr)
return;
Delete(root->_left);
Delete(root->_right);
delete root;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << ":" << root->_value << endl;
_InOrder(root->_right);
}
private:
Node* _root;
};
假设，实现一个简单的英汉词典dict，可以通过英文找到与其对应的中文。
我们可以采用KV模型实现。
void TestBSTree4()
{
KV::BSTree<string ,string> kv;
kv.Insert("sort", "排序");
kv.Insert("search", "搜索");
kv.Insert("left", "左边");
kv.Insert("right", "右边");
string str;
while (cin >> str)
{
auto* ptr = kv.Find(str);
if (ptr)
{
cout << ptr->_key << ":" << ptr->_value << endl;
}
else
{
cout << "无此单词" << endl;
}
}
}
统计每样水果出现的次数
void TestBSTree5()
{
// 统计水果出现的次数
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };
KV::BSTree<string, int> count;
for (const auto& str : arr)
{
// 先查找水果在不在搜索树中
// 1、不在，说明水果第一次出现，则插入<水果, 1>
// 2、在，则查找到的节点中水果对应的次数++
auto* ret = count.Find(str);
if (ret == nullptr)
{
count.Insert(str, 1);
}
else
{
ret->_value++;
}
}
count.InOrder();
}
KV搜索模型------>通过一个值去查找或者修改另一个值。
那以后想用二叉搜索树难道要手撕一个出来吗？
其实后面学的map对应KV模型，set对应模型，不用担心。
7.二叉搜索树的性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：
l
o
g
2
N
log_2 N
log2N
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为： N 2 \frac{N}{2} 2N
问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？
那么我们后续学习的AVL树和红黑树就可以上场了。
