C++二叉搜索树与KV模型
二叉搜索树与KV模型
二叉搜索树
本章是为了C++的map和set做铺垫
概念与操作
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树: 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
二叉搜索树的查找
a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。 b、最多查找高度次，走到到空，还没找到，这个值不存在。
二叉搜索树的插入
a. 树为空，则直接新增节点，赋值给root指针。 b. 树不空，按二叉搜索树性质查找插入位置，插入新节点。
其实上面两个还是很容易实现的，最难的是删除这里，要考虑三种情况： 删除的是叶子结点，那就找到直接释放就好了。 删除的是只有一个左/右孩子的结点，那就先链接父亲结点和左/右孩子结点，然后直接删除该节点。 其实删除叶子结点可以和删除一个孩子结点的合并，因为叶子节点两个都是空，删除一个孩子的结点只有一个是空。 删除两个孩子结点的最麻烦，首先要找到替换这个结点的值，肯定是左子树最大的或者是右子树最小的。（二选一都可以，这里我选择左子树最小的）
性能分析
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数，即结点越深，则比较次数越多。 但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：
其实二叉搜索树是一个不完整的树，遇到这种极端情况就没有办了，后面的AVL和红黑树会完成这个功能。
实现
实现这里我会写出某些成员函数的递归与迭代版本。 其实最难的是删除步骤：
如果是删除叶子结点直接删除就可以，只有一个孩子的就先看是只有左孩子还是只右有孩子，如果只有左孩子就让父节点的指针指向左孩子，如果只有右孩子就让父亲的指针指向右孩子，然后判断要删除的结点在父节点的左子树还是右子树，才能判断让父节点的左指针还是右指针去链接孩子。 但是这个思路还要考虑这种情况：
如果删除了根节点，那么就要换根。
如果是有两个孩子的就非常难办了，首先要去替换，这里用左子树的最小节点去替换。 先来看看第一种情况：
删除3，首先让3和左子树的最小值4交换（赋值也行），然后让cur记住原来是3这里，再来一个指针记录原来是4这里，再用parent指向父节点6的位置：
然后删除minright之前，将parent的左指针指向minright的右指针，因为minright左指针肯定是没有值了，但是右指针不一定没有。 然后是第二种情况： 删除的是根，这里只能和10交换，parent就是根，10就是minright，释放minright之前要将parent的右与minright的右链接起来。
迭代
#include<iostream>
#include<vector>
using namespace std;
template<class K>
struct BSTNode//树结点
{
BSTNode(K key)
:_key(key)
,left(nullptr)
,right(nullptr)
{}
K _key;//结点值
BSTNode<K>* left;//左子树
BSTNode<K>* right;//右子树
};
template<class K>
class BSTree//树
{
typedef BSTNode<K> Node;
public:
BSTree()
:_root(nullptr)
{}
bool Insert(const K& key)//插入数据
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
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
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;
if (cur == nullptr)
{
return false;
}
while (cur)
{
if (cur->_key > key)
cur = cur->left;
else if (cur ->_key < key)
cur = cur->right;
else
{
return true;
}
}
return false;
}
bool Erase(const K& key)//删除数据
{
if (_root == nullptr)
{
return false;
}
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;
}
delete cur;//释放结点
}
else if (cur->right == nullptr)//只有左孩子
{
if (cur == _root)
{
_root = cur->left;
}
else if (parent->left == cur)
{
parent->left = cur->left;
}
else
{
parent->right = cur->left;
}
delete cur;//释放结点
}
else//有两个孩子
{
Node* minright = cur->right;
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;
}
void _InOrder()//因为不想让外界访问道内部的_root，所以只能通过成员函数内部访问
{
InOrder(_root);
cout << endl;
}
private:
void InOrder(Node* root)//中序遍历
{
if (root == nullptr)
{
return;
}
InOrder(root->left);
cout << root->_key << ' ';
InOrder(root->right);
}
Node* _root;//树的根结点
};递归 递归的函数都要带头结点，也就是说又要去调用子函数的方式来调用对应的递归函数。 查找：
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;
}递归这里有些地方很巧妙： 插入：
bool InsertR(Node*& root, const K& key)//这里的root用了引用
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
if (_root->_key < key)
InsertR(_root->right, key);
else if (_root->_key > key)
InsertR(_root->left, key);
else
return false;
}为什么这里的头结点用了引用呢？是因为解决链接问题的：
假设这里插入了一个6，应该是在5的右孩子那里，当我们找到位置的时候，上一层传递的是5的右指针，用了引用就是5的右指针的别名，开辟空间之后直接让5的右指针就能指向这块空间。 删除：
bool EraseR(Node*& root, const K& key)
{
if (root == nullptr)
return false;
if (root->_key > key)
return EraseR(root->left, key);
else if (root->_key < key)
return EraseR(root->right, key);
else
{
Node* cur = root;
if (root->right == nullptr)//只有左孩子
{
root = root->left;//这里不仅仅找到的是key，也是父节点指向该节点的指针别名
}
else if (root->left == nullptr)//只有右孩子
{
root = root->right;//这里也不用担心删除的是根，直接就将_root指向了下一个结点
}
else//有两个孩子，这里的引用root就不管用了，因为引用不能改指向，在这里往下找右树最小值是行不通的
{
Node* parent = root->right;//去该节点的右子树查找最小值
while (parent->left)
{
parent = parent->left;
}
swap(parent->_key, root->_key);//交换两个值
return EraseR(root->right, key);//再次去找该节点最小值，也就是被交换的值，然后进行删除
}
delete cur;
return true;
}
return false;
}
析构
void Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->left);
Destroy(root->right);
delete root;
}拷贝 拷贝函数不能去一个一个插入：
所以说，这里只要去前序遍历，然后遇到一个结点拷贝一个结点就可以了。
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* cur = new Node(root->_key);
cur->left = Copy(root->left);
cur->right = Copy(root->right);
return cur;//这里将新开辟的结点返回给上一层，让上一层的指针指向这里，就能连接起来
}KV模型
KV模型前身还有一个K（key）模型，就是上面的搜索二叉树，比如说要检查一个英语单词写的对不对，就要创建一个词库（搜索二叉树）里面找。 KV（key/value）模型是我们去查找一个英语单词的汉译，不可能在庞大的库中一个一个寻找词汇，而是通过搜索二叉树的形式寻找，那么一个单词相对应一个汉译，这个模型叫做KV模型。 其实本质就是一个结点有两个值而已。 这里的查找就很有用了，举个例子，一个学生来图书馆借书，借了多少本书需要知道，这本书归还没有也需要知道，所以这里查找也顺便进行修改。
#include<iostream>
#include<vector>
#include<string>
using namespace std;
template<class K, class V>
struct BSTNode//树结点
{
BSTNode(const K& key, const V& value)
:_key(key)
,_value(value)
, left(nullptr)
, right(nullptr)
{}
K _key;
V _value;
BSTNode<K, V>* left;//左子树
BSTNode<K, V>* right;//右子树
};
template<class K, class V>
class BSTree//树
{
typedef BSTNode<K, V> Node;
public:
BSTree()
:_root(nullptr)
{}
~BSTree()
{
Destroy(_root);
_root = nullptr;
}
bool Insert(const K& key, const V& value)//插入数据
{
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}
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
return false;
}
cur = new Node(key, value);
if (parent->_key > key)
parent->left = cur;
else
parent->right = cur;
return true;
}
Node* Find(const K& key)//查找
{
Node* cur = _root;
if (cur == nullptr)
{
return nullptr;
}
while (cur)
{
if (cur->_key > key)
cur = cur->left;
else if (cur->_key < key)
cur = cur->right;
else
{
return cur;//找到就返回该节点
}
}
return nullptr;
}
bool Erase(const K& key)//删除数据
{
if (_root == nullptr)
{
return false;
}
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;
}
delete cur;//释放结点
}
else if (cur->right == nullptr)//只有左孩子
{
if (cur == _root)
{
_root = cur->left;
}
else if (parent->left == cur)
{
parent->left = cur->left;
}
else
{
parent->right = cur->left;
}
delete cur;//释放结点
}
else//有两个孩子
{
Node* minright = cur->right;
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;
}
}
}
void _InOrder()//因为不想让外界访问道内部的_root，所以只能通过成员函数内部访问
{
InOrder(_root);
cout << endl;
}
bool _FindR(const K& key)
{
return FindR(_root, key);
}
private:
void Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->left);
Destroy(root->right);
delete root;
}
void InOrder(Node* root)//中序遍历
{
if (root == nullptr)
{
return;
}
InOrder(root->left);
cout << root->_key << ' ';
cout << root->_value << ' ';
InOrder(root->right);
}
Node* _root;//树的根结点
};
void test()
{
BSTree<string, string> tree;
tree.Insert("1", "one");
tree.Insert("2", "two");
tree.Insert("3", "three");
tree.Insert("4", "four");
tree.Insert("5", "five");
BSTNode<string, string>* ret;//储存返回查找到结点的值
string str;
while (cin >> str)
{
ret = tree.Find(str);
if (ret)
cout << ret->_value << endl;
else
cout << "没有此结果" << endl;
}
}
腾讯云开发者
