二叉搜索树
二叉搜索树概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
int a [] = {5,3,4,1,7,8,2,6,0,9};
仔细观察这颗搜索二叉树，它的中序遍历实际上是构成一个升序的排序的，所以二叉搜索树也叫二叉排序树
二叉搜索树操作
-
二叉搜索树的查找
-
二叉搜索树的插入
插入的具体过程如下：-
树为空，则直接插入
-
树不空，按二叉搜索树性质查找插入位置，插入新节点
-
-
二叉搜索树的删除
首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：- 要删除的结点无孩子结点(也就是叶子节点)
- 要删除的结点只有左孩子结点
- 要删除的结点只有右孩子结点
- 要删除的结点有左、右孩子结点
看起来待删除节点有4种情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：
- 情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点
- 情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点
- 情况d：在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题
二叉搜索树的实现
//节点的创建
template<class T>
struct BSTNode {//Binary Search Tree
BSTNode* _left;
BSTNode* _right;
T _val;
//构造
BSTNode(const T& val = T())
:_left(nullptr)
,_right(nullptr)
,_val(val)
{}
};
//搜索树的实现
template<class T>
class BSTree {
typedef BSTNode<T> node;
typedef BSTNode<T>* pnode;
private:
pnode root = nullptr;
public:
BSTree()
: root(nullptr)
{}
void _Destroy(pnode node)
{
if (node == nullptr)
return;
_Destroy(node->_left);
_Destroy(node->_right);
delete node;
node = nullptr;
}
~BSTree()
{
_Destroy(root);
}
//判空
bool empty()
{
return root == nullptr;
}
//插入
//如果树里面没有该元素，则进行插入，返回true
//如果树里面已经有该元素了，则不插入，返回false
bool insert(const T& val)
{
//树为空时直接插入
if (root == nullptr)
{
root = new node(val);
return true;
}
pnode parent = nullptr;
pnode cur = root;
while (cur)
{
//向左边找插入位置
if (val < cur->_val)
{
parent = cur;
cur = cur->_left;
}
else if (val > cur->_val)//向左边找插入位置
{
parent = cur;
cur = cur->_right;
}
else//该值已存在，不用插入
{
return false;
}
}
//找到后开始插入
cur = new node(val);
//判断是插在左节点还是右节点
if (parent->_val > val)//插在左边
{
parent->_left = cur;
}
else//插在右边
{
parent->_right = cur;
}
return true;
}
void _order(pnode& root)
{
if (root == nullptr)
return;
_order(root->_left);
cout << root->_val << " ";
_order(root->_right);
}
//中序遍历
void order()
{
_order(root);
cout << endl;
}
//查找
bool find(const T& val)
{
pnode cur = root;
while (cur)
{
//向左边查找
if (cur->_val > val)
{
cur = cur->_left;
}
else if (cur->_val < val)//向右边查找
{
cur = cur->_right;
}
else//找到了
{
return true;
}
}
return false;
}
//删除节点
bool erase(const T& val)
{
assert(!empty());
pnode cur = root;
pnode parent = nullptr;
//先找到该节点
while (cur)
{
if (cur->_val > val)//往左边找
{
parent = cur;
cur = cur->_left;
}
else if (cur->_val < val)//往右边找
{
parent = cur;
cur = cur->_right;
}
else//找到了
{
//判断左右子树是否为空
//1.左子树为空，parent接上它的右子树
//2.右子树为空，parent接上它的左子树
//3.左右子树都不为空，进行替换删除
if (cur->_left == nullptr)
{
if (cur == root)//删除的是根节点且左树为空，直接让右结点成为根
{
root = root->_right;
}
else
{
//判断cur是parent的左节点还是右节点
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == root)//删除的是根节点且右树为空，直接让左结点成为根
{
root = root->_left;
}
else
{
//判断cur是parent的左节点还是右节点
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
else//左右子树都不为空
{
//往右边找最小的节点进行替换
pnode RightMin = cur->_right;
pnode RightMinParent = cur;
//一直往左边找
while (RightMin->_left)
{
RightMinParent = RightMin;
RightMin = RightMin->_left;
}
//找到后，将该值与cur的值进行替换
cur->_val = RightMin->_val;
//将替换节点的右子树接到替换节点父亲的左子树或右子树位置
//判断MIn是Parent的哪个节点
if (RightMinParent->_left == RightMin)
{
RightMinParent->_left = RightMin->_right;
}
else
{
RightMinParent->_right = RightMin->_right;
}
delete RightMin;
}
return true;
}
}
return false;//没找到
}
};
删除左右节点都不为空的节点时，替换节点的右子树不一定接到它的父节点的右节点上，比如删除7，找到8为右子树的最小节点，7是它的父节点，8的右子树应该接到7的右边，而不是左边。所以在接替换节点的右子树之前，要判断是接在其父节点的左边还是右边
先删7有问题
当只有一个节点时，删除会引用parent，让删除节点的左右子树接到parent的左边或右边，而此时parent为空，访问它的左右子树是非法的，所以需要对只有一个节点的树进行特殊判断。
二叉搜索树的应用
-
K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：- 以单词集合中的每个单词作为key，构建一棵二叉搜索树
- 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
-
KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。比如：实现一个简单的英汉词典dict，可以通过英文找到与其对应的中文，具体实现方式如下：
-
<单词，中文含义>为键值对构造二叉搜索树，注意：二叉搜索树需要比较，键值对比较时只比较Key
-
查询英文单词时，只需给出英文单词，就可快速找到与其对应的key
//节点的创建 template<class K,class V> struct BSTNode {//Binary Search Tree BSTNode* _left; BSTNode* _right; K _key; V _val; //构造 BSTNode(const K& key = K(), const V& val = V()) :_left(nullptr) , _right(nullptr) ,_key(key) , _val(val) {} }; //搜索树的实现 template<class K, class V> class BSTree { typedef BSTNode<K, V> node; typedef BSTNode<K, V>* pnode; private: pnode root = nullptr; public: BSTree() : root(nullptr) {} void _Destroy(pnode node) { if (node == nullptr) return; _Destroy(node->_left); _Destroy(node->_right); delete node; node = nullptr; } ~BSTree() { _Destroy(root); } //判空 bool empty() { return root == nullptr; } //插入 //如果树里面没有该元素，则进行插入，返回true //如果树里面已经有该元素了，则不插入，返回false bool insert(const K& key, const V& val) { //树为空时直接插入 if (root == nullptr) { root = new node(key, val); return true; } pnode parent = nullptr; pnode cur = root; while (cur) { //向左边找插入位置 if (key < cur->_key) { parent = cur; cur = cur->_left; } else if (key > cur->_key)//向左边找插入位置 { parent = cur; cur = cur->_right; } else//该值已存在，不用插入 { return false; } } //找到后开始插入 cur = new node(key, val); //判断是插在左节点还是右节点 if (parent->_key > key)//插在左边 { parent->_left = cur; } else//插在右边 { parent->_right = cur; } return true; } void _order(pnode& root) { if (root == nullptr) return; _order(root->_left); cout << root->_key << "->" << root->_val <<endl; _order(root->_right); } //中序遍历 void order() { _order(root); cout << endl; } //查找 pnode find(const K& key) { pnode cur = root; 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) { assert(!empty()); pnode cur = root; pnode parent = nullptr; //先找到该节点 while (cur) { if (cur->_key > key)//往左边找 { parent = cur; cur = cur->_left; } else if (cur->_key < key)//往右边找 { parent = cur; cur = cur->_right; } else//找到了 { //判断左右子树是否为空 //1.左子树为空，parent接上它的右子树 //2.右子树为空，parent接上它的左子树 //3.左右子树都不为空，进行替换删除 if (cur->_left == nullptr) { if (cur == root)//删除的是根节点且左树为空，直接让右结点成为根 { root = root->_right; } else { //判断cur是parent的左节点还是右节点 if (parent->_left == cur) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } delete cur; } else if (cur->_right == nullptr) { if (cur == root)//删除的是根节点且右树为空，直接让左结点成为根 { root = root->_left; } else { //判断cur是parent的左节点还是右节点 if (parent->_left == cur) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; } else//左右子树都不为空 { //往右边找最小的节点进行替换 pnode RightMin = cur->_right; pnode RightMinParent = cur; //一直往左边找 while (RightMin->_left) { RightMinParent = RightMin; RightMin = RightMin->_left; } //找到后，将该值与cur的值进行替换 cur->_key = RightMin->_key; cur->_val = RightMin->_val; //将替换节点的右子树接到替换节点父亲的左子树或右子树位置 //判断MIn是Parent的哪个节点 if (RightMinParent->_left == RightMin) { RightMinParent->_left = RightMin->_right; } else { RightMinParent->_right = RightMin->_right; } delete RightMin; } return true; } } return false;//没找到 } };
-
字典的测试
//字典测试
void TestDic()
{
BSTree<string, string> bst;
bst.insert("hello", "你好");
bst.insert("goodbye", "再见");
bst.insert("kobe", "科比");
bst.insert("buy", "买");
bst.insert("insert", "插入");
bst.insert("sort", "排序");
bst.insert("tree", "树");
bst.order();
auto result = bst.find("kobe");
cout << result->_key << "->" << result->_val << endl << endl;
bst.erase("hello");
bst.erase("goodbye");
bst.erase("sort");
bst.erase("tree");
bst.erase("buy");
bst.order();
}
统计数组中名字出现次数
//统计数组中学生名字的个数
void TestCountName()
{
BSTree<string, int> bst;//int统计出现次数
const char* arr[] = {"张三", "李四", "王五", "赵六","张三", "张三", "张三", "李四" ,"李四" ,"赵六" };
for (auto e : arr)
{
BSTNode<string, int>* ret = bst.find(e);
//树中没有该名字
if (ret == nullptr)
bst.insert(e, 1);//将出现次数设置为1
else//已经出现过了
bst.insert(e, ret->_val++);
}
bst.order();
}
二叉搜索树的性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：log2(N)
最差情况下，二叉搜索树退化为单支树，其平均比较次数为： N/2
问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，都可以是二叉搜索树的性能最佳？
用平衡树解决->AVL树、红黑树