二叉搜索树概述
二叉搜索树是一种具有特殊性质的二叉树。二叉搜索树可以是一棵空树，若不为空树，其：
- 若左子树不为空，则左子树所有的节点值小于根节点值；
- 若右子树不为空，则右子树所有的节点值大于根节点值。
与二叉树一样，二叉搜索树也是递归定义的，二叉搜索树的左右子树都是二叉搜索树。
二叉搜索树的结构
二叉搜索树的结构是一棵二叉树，其左子树的节点值都小于根节点值，右子树的节点值都大于根节点值。二叉搜索树使用链式结构进行实现。
两种二叉搜索树及定义
二叉搜索树常用有两种模型：Key模型和Key-Value模型。
Key模型的二叉搜索树的节点只需要存储一个关键码Key即可，可以将关键码理解为需要搜索的值。这种模型主要用于解决快速判断一个值在不在集合中的问题。
template<typename Key>
struct BinarySearchTreeNode
{
typedef BinarySearchTreeNode<Key> BST_Node;
BinarySearchTreeNode(const Key& val)
:_left(nullptr),
_right(nullptr),
_val(val)
{ };
BST_Node* _left;
BST_Node* _right;
Key _val; //只存储一个关键码
};
template<typename Key>
class BinarySearchTree
{
private:
typedef BinarySearchTreeNode<Key> BST_Node;
typedef BinarySearchTree<Key> Self;
/*…………*/
private:
BST_Node* _root; //维护根节点
};Key-Value模型的二叉搜索树的节点除了要存储关键码Key之外，还需要存储对应的键值Value，即需要存储一个(Key, Value)的键值对。这种模型主要用于解决通过一个值找另外一个值的映射问题。
template<typename Key, typename Value>
struct BinarySearchTreeNode
{
typedef BinarySearchTreeNode<Key, Value> BST_Node;
BinarySearchTreeNode<Key, Value>(const Key& k, const Value& v)
:_key(k), _val(v),
_left(nullptr), _right(nullptr)
{ }
Key _key;
Value _val; //存储一个键值对
BST_Node* _left;
BST_Node* _right;
};
template<typename Key, typename Value>
class BinarySearchTree
{
private:
typedef BinarySearchTreeNode<Key, Value> BST_Node;
/*…………*/
private:
BST_Node* _root;
};上述的两种模型，前者是STL set的基本实现思路，后者是STL map的基本实现思路，二者的Key值都具有互异性，不允许重复。
二叉搜索树的接口实现
作为一种具有特殊性质的二叉树，二叉搜索树的接口大体上有两种实现方式：迭代方式实现和递归方式实现。下面的实现以Key-Value模型为例，Key模型与此类似。
迭代方式实现
template<typename Key, typename Value>
struct BinarySearchTreeNode
{
typedef BinarySearchTreeNode<Key, Value> BST_Node;
BinarySearchTreeNode<Key, Value>(const Key& k, const Value& v)
:_key(k), _val(v),
_left(nullptr), _right(nullptr)
{ }
Key _key;
Value _val;
//存储一个键值对
BST_Node* _left;
BST_Node* _right;
};
template<typename Key, typename Value>
class BinarySearchTree
{
private:
typedef BinarySearchTreeNode<Key, Value> BST_Node;
typedef BinarySearchTree<Key, Value> Self;
public:
BinarySearchTree()
:_root(nullptr)
{ }
BinarySearchTree(const Self& BSTree)
{
//递归进行拷贝构造
_root = _copyConstruct(BSTree);
}
~BinarySearchTree()
{
Destroy(_root); //递归销毁二叉树
}
//现代写法的赋值重载
Self& operator=(Self BSTree) const
{
std::swap(_root, BSTree._root);
return *this;
}
bool Insert(const Key& key, const Value& val)
{
//树为空的情况单独处理
if (Empty()) {
_root = new BST_Node(key, val);
}
BST_Node* cur = _root;
BST_Node* parent = nullptr;
//寻找合适的插入位置
while (cur)
{
if (key < cur->_key) {
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key) {
parent = cur;
cur = cur->_right;
}
else {
return false;
}
}
BST_Node* newNode = new BST_Node(key, val);
//插入新节点
//由于不能判断此时cur相对于parent的位置，所以需要再次判断
if (key < parent->_key) {
parent->_left = newNode;
}
else {
parent->_right = newNode;
}
return true;
}
bool Erase(const Key& key)
{
BST_Node* pos = _root;
BST_Node* parent = nullptr;
//寻找目标节点
while (pos)
{
if (key < pos->_key) {
parent = pos;
pos = pos->_left;
}
else if (key > pos->_key) {
parent = pos;
pos = pos->_right;
} //找到目标节点
else
{
/*
删除节点分三种情况：
1.需要删除的节点的子树数量为 0
2.需要删除的节点的子树数量为 1
3.需要删除的节点的子树数量为 2
对于前两种情况，将子树移交给目标节点的父节点；
对于第三种情况，寻找合适的临时节点替代目标节点，并删除临时节点
*/
if (pos->_left == nullptr)
{
//目标位置为根节点的情况需要独自处理
if (pos == _root) {
_root = pos->_right;
}
else
{
if (pos == parent->_left) {
parent->_left = pos->_right;
}
else {
parent->_right = pos->_right;
}
}
}
else if (pos->_right == nullptr)
{
if (pos == _root) {
_root = pos->_left;
}
else
{
if (pos == parent->_left) {
parent->_left = pos->_left;
}
else {
parent->_right = pos->_left;
}
}
}
else
{
BST_Node* cur = pos->_left;
BST_Node* parent = cur;
//寻找目标节点的左子树的最右节点，以此节点作为临时节点
while (cur->_right) {
parent = cur;
cur = cur->_right;
}
//交换节点的键值对以进行替换
std::swap(cur->_key, pos->_key);
std::swap(cur->_val, pos->_val);
//删除临时节点
//此处依然需要进行一次判断，因为不确定临时节点的位置
//临时虽然是左子树的最右节点，但是并非一定是其父节点的右孩子
if (cur->_left == nullptr)
{
if (cur == parent->_left) {
parent->_left = cur->_right;
}
else {
parent->_right = cur->_right;
}
}
else
{
if (cur == parent->_left) {
parent->_left = cur->_left;
}
else {
parent->_right = cur->_left;
}
}
}
return true;
}
}
return false;
}
BST_Node* Find(const Key& key) const
{
BST_Node* cur = _root;
//根据二叉搜索树的性质进行搜索
while (cur)
{
if (key < cur->_key) {
cur = cur->_left;
}
else if (key > cur->_key) {
cur = cur->_right;
}
else {
return cur;
}
}
return nullptr;
}
bool Empty() const
{
return _root == nullptr;
}
void InOrder() const
{
_InOrder(_root);
}
private:
BST_Node* _copyConstruct(BST_Node* BSTreeRoot)
{
if (BSTreeRoot == nullptr) {
return nullptr;
}
BST_Node* root = new BST_Node(BSTreeRoot->_key, BSTreeRoot->_val);
root->_left = _copyConstruct(BSTreeRoot->_left);
root->_right = _copyConstruct(BSTreeRoot->_right);
return root;
}
void Destroy(BST_Node* root)
{
if (root == nullptr) {
return;
}
Destroy(root->_left);
Destroy(root->_right);
delete root;
root = nullptr;
}
void _InOrder(const BST_Node* root) const
{
if (root == nullptr) {
return;
}
_InOrder(root->_left);
cout << root->_val << ' ';
_InOrder(root->_right);
}
private:
BST_Node* _root;
};递归方式实现
template<typename Key, typename Value>
struct BinarySearchTreeNode
{
typedef BinarySearchTreeNode<Key, Value> BST_Node;
BinarySearchTreeNode<Key, Value>(const Key& k, const Value& v)
:_key(k), _val(v),
_left(nullptr), _right(nullptr)
{ }
Key _key;
Value _val;
BST_Node* _left;
BST_Node* _right;
};
template<typename Key, typename Value>
class BinarySearchTree
{
private:
typedef BinarySearchTreeNode<Key, Value> BST_Node;
public:
BinarySearchTree()
:_root(nullptr)
{ }
~BinarySearchTree()
{
Destroy(_root);
}
//下面的接口都在子函数中进行递归调用
bool Insert(const Key& key, const Value& val)
{
return _insert(key, val, _root);
}
bool Erase(const Key& key)
{
return _erase(key, _root);
}
BST_Node* Find(const Key& key) const
{
return _find(key, _root);
}
bool Empty() const
{
return _root == nullptr;
}
void InOrder() const
{
_InOrder(_root);
}
private:
//使用root指针的引用，使root与上层栈帧的指针保持关联，便于节点的链接
bool _erase(const Key& key, BST_Node*& root)
{
if (root == nullptr) {
return false;
}
if (key < root->_key) {
return _erase(key, root->_left);
}
else if (key > root->_key) {
return _erase(key, root->_right);
}
else
{
BST_Node* delNode = root;
if (root->_left == nullptr) {
root = root->_right;
delete delNode;
}
else if (root->_right == nullptr) {
root = root->_left;
delete delNode;
}
else
{
//寻找左子树的最大节点
BST_Node* leftMax = root->_left;
while(leftMax->_right) {
leftMax = leftMax->_right;
}
std::swap(leftMax->_key, root->_key);
std::swap(leftMax->_val, root->_val);
//此处可以直接递归删除关键码为key临时节点
return _erase(key, root->_left);
}
return true;
}
}
//使用root指针的引用，使root与上层栈帧的指针保持关联，便于节点的链接
bool _insert(const Key& key, const Value& val, BST_Node*& root)
{
if (root == nullptr)
{
root = new BST_Node(key, val);
return true;
}
if (key < root->_key) {
return _insert(key, val, root->_left);
}
else if (key > root->_key) {
return _insert(key, val, root->_right);
}
else if (key == root->_key) {
return false;
}
}
BST_Node* _find(const Key& key, BST_Node* root) const
{
if (root == nullptr || key == root->_key) {
return root;
}
//任意子树找到即返回
BST_Node* ret_left = _find(key, root->_left);
if (ret_left) {
return ret_left;
}
BST_Node* ret_right = _find(key, root->_right);
if (ret_right) {
return ret_right;
}
}
void Destroy(BST_Node* root)
{
if (root == nullptr) {
return;
}
Destroy(root->_left);
Destroy(root->_right);
delete root;
root = nullptr;
}
void _InOrder(const BST_Node* root) const
{
if (root == nullptr) {
return;
}
_InOrder(root->_left);
cout << root->_val << ' ';
_InOrder(root->_right);
}
private:
BST_Node* _root;
};二叉搜索树实现细节
无论是迭代写法还是递归写法，二叉搜索树的erase()接口都相对麻烦，需要分三种情况进行考虑(如上面代码中的注释所述)。在转交子树和删除结点的过程中，要全面地考虑节点可能的分布情况，若一欲贪图方便就会产生意料不到的问题。例如删除具有两棵子树的节点，最后删除临时节点时依旧需要判断临时节点的位置。
