本篇文章将介绍一种功能更加强大的二叉树——二叉搜索树。 相比于普通的二叉树,二叉搜索树在很多方面都有优势,尤其是在查找数据上效率明显提高,并且通过中序遍历二叉搜索树它所存储的数据是有序的。
二叉搜索树,是一种特殊的二叉树结构,它或为空树,或者满足以下性质:
二叉搜索树和普通二叉树的框架差不太多,需要一个节点类,再封装一个完成二叉搜索树功能的类就行。
template<class K>
struct BSTNode
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
//构造
BSTNode(const K& key)
:_key(key)
,_left(nullptr)
,_right(nullptr)
{}
};
template<class K>
class BSTree
{
typedef BSTNode<K> Node;
public:
//查找
bool Find(const K& key)
{}
//插入
bool Insert(const K& key)
{}
//删除
bool Erase(const K& key)
{}
//中序遍历
void InOrder()
{}
private:
//用一个节点指针来管理二叉搜索树,缺省值为nullptr
Node* _root = nullptr;
};
插入数据要始终保持二叉搜索树的特点。另外二叉搜索树中的数据通常不允许重复 ,所以如果要插入的数据在二叉搜索树中已经存在,则插入错误。
| 实现:
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->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
if (parent->_key > key)
{
parent->_left = new Node(key);
}
else
{
parent->_right = new Node(key);
}
}
从根开始比较查找,比根大则往右边查找,比根小则往左边查找。最多查找高度次,走到到空还没找到,这个值不存在。
| 实现:
bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key < cur->_key)
{
cur = cur->_left;
}
else if (key > cur->_key)
{
cur = cur->_right;
}
else
{
return true;
}
}
return false;
}
其中n是树中节点的数量。然而,在最坏的情况下(即树退化为链表时),时间复杂度会变为O(n)。为了保持查找效率,通常会使用平衡二叉搜索树(如AVL树、红黑树等),它们通过自平衡操作来确保树的高度保持在对数级别,在后续的文章中会介绍。
在二叉搜索树中删除一个节点是一个稍微复杂的过程,因为它需要确保删除操作后树仍然保持二叉搜索树的属性。
nullptr
从上面两种不同的情况来看,找到目标节点右子树中的最小节点后,这个最小节点是它父节点的左孩子还是右孩子都是有可能的,所以在替换掉目标节点的值后,删除右子树中的最小节点之前,需要判断一下右子树中的最小节点的孩子是跟在其父节点的左还是右。
| 实现:
bool Erase(const K& key)
{
Node* cur = _root;
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//找到要删除的节点
{
//没有孩子或一个孩子
if (cur->_left == nullptr)
{
if (_root->_key == key)
{
_root = _root->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else if (parent->_right == cur)
{
parent->_right = cur->_right;
}
}
delete cur;
cur = nullptr;
return true;
}
else if (cur->_right == nullptr)
{
if (_root->_key == key)
{
_root = _root->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else if (parent->_right == cur)
{
parent->_right = cur->_left;
}
}
delete cur;
cur = nullptr;
return true;
}
//有两个孩子
else
{
//用要删除节点的右子树的最小节点代替删除节点
parent = cur;
Node* MinNode = cur->_right;
while (MinNode->_left)
{
parent = MinNode;
MinNode = MinNode->_left;
}
cur->_key = MinNode->_key;
if (parent->_left == MinNode)
{
parent->_left = MinNode->_right;
}
else
{
parent->_right = MinNode->_right;
}
delete MinNode;
return true;
}
}
}
return false;
}
找到要删除的节点后,删除之前有几个值得特别注意的点:
二叉搜索树的中序遍历和普通二叉树的中序遍历是一样的。
void InOrder(const Node* root)
{
if (root == nullptr)
{
return;
}
InOrder(root->_left);
cout << root->_key << " ";
InOrder(root->_right);
}
但是这样写有一个问题,当我们调用中序遍历函数时,需要传一个二叉搜索树的根节点指针,而_root
是BSTree
类中的私有成员变量,在类外面不能使用,所以我们需要想一些办法。
既然类的私有成员变量在类外面不能使用,那我们就不在类外面使用了,可以通过函数调用在类里面间接的使用_root
成员变量。
template<class K>
class BSTree
{
typedef BSTNode<K> Node;
public:
//查找
bool Find(const K& key)
{}
//插入
bool Insert(const K& key)
{}
//删除
bool Erase(const K& key)
{}
//中序遍历
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(const Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
Node* _root = nullptr;
};
template<class K>
struct BSTNode
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
BSTNode(const K& key)
:_key(key)
,_left(nullptr)
,_right(nullptr)
{}
};
template<class K>
class BSTree
{
typedef BSTNode<K> Node;
public:
bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key < cur->_key)
{
cur = cur->_left;
}
else if (key > cur->_key)
{
cur = cur->_right;
}
else
{
return true;
}
}
return false;
}
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->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
if (parent->_key > key)
{
parent->_left = new Node(key);
}
else
{
parent->_right = new Node(key);
}
}
bool Erase(const K& key)
{
Node* cur = _root;
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//找到要删除的节点
{
//没有孩子或一个孩子
if (cur->_left == nullptr)
{
if (_root->_key == key)
{
_root = _root->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else if (parent->_right == cur)
{
parent->_right = cur->_right;
}
}
delete cur;
cur = nullptr;
return true;
}
else if (cur->_right == nullptr)
{
if (_root->_key == key)
{
_root = _root->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else if (parent->_right == cur)
{
parent->_right = cur->_left;
}
}
delete cur;
cur = nullptr;
return true;
}
//有两个孩子
else
{
//用要删除节点的右子树的最小节点代替删除节点
parent = cur;
Node* MinNode = cur->_right;
while (MinNode->_left)
{
parent = MinNode;
MinNode = MinNode->_left;
}
cur->_key = MinNode->_key;
if (parent->_left == MinNode)
{
parent->_left = MinNode->_right;
}
else
{
parent->_right = MinNode->_right;
}
delete MinNode;
return true;
}
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(const Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
Node* _root = nullptr;
};
二叉搜索树不需要我们显示去写构造,根节点指针给缺省值nullptr,用编译器默认生成的构造就可。而拷贝构造需要我们自己去实现深拷贝,因为编译器默认生成的拷贝构造是浅拷贝,不符合我们的要求。
但是,我们知道编译器生成默认构造的规则是:我们不写构造函数,编译器就会生成一个默认构造函数,而拷贝构造也是构造,我们写了拷贝构造后编译器就不再生成默认构造了,所以我们还是需要写一个默认构造,只需要形式的写一个就行。可以考虑用:BSTree() = default;
。当我们使用 =default
时,意思是告诉编译器:“我知道这个成员函数可以有默认实现,请帮我生成它。”
二叉搜索树的拷贝构造用递归实现会比较简单,需要传根节点的指针,而拷贝构造函数我们知道传过来的是对象的引用,所以我们可以再包装一下,写一个拷贝函数。
//默认构造
BSTree() = default;
//拷贝构造
BSTree(const BSTree<K>& t)
{
_root = copy(t._root);
}
Node* copy(Node* root)
{
if (root == nullptr)
{
return nullptr;
}
Node* NewRoot = new Node(root->_key);
NewRoot->_left = copy(root->_left);
NewRoot->_right = copy(root->_right);
return NewRoot;
}
走的是后序遍历拷贝二叉树。
同样的,析构函数不需要传参数,而我们想析构二叉搜索树就必须传根节点指针,那么也可以用销毁节点的函数再包装一下。
~BSTree()
{
Destroy(_root);
_root = nullptr;
}
void Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
走的也是后序遍历析构二叉搜索树。
在K模型中,每个节点仅存储一个关键码(即Key),这个关键码用于确定节点在树中的位置,并满足二叉搜索树的性质。
我们上面实现的二叉搜索树就是一个简单的Key模型。
定义:
应用场景:
这里我们以上面实现的二叉搜索树为基础,实现一个简单词典的KV模型。
template<class K, class V>
struct BSTNode
{
K _key;
V _value;
BSTNode<K, V>* _left;
BSTNode<K, V>* _right;
BSTNode(const K& key, const V& value)
:_key(key)
,_value(value)
, _left(nullptr)
, _right(nullptr)
{}
};
template<class K, class V>
class BSTree
{
typedef BSTNode<K, V> Node;
public:
BSTree() = default;
BSTree(const BSTree<K, V>& t)
{
_root = copy(t._root);
}
Node* copy(Node* root)
{
if (root == nullptr)
{
return nullptr;
}
Node* NewRoot = new Node(root->_key, root->_value);
NewRoot->_left = copy(root->_left);
NewRoot->_right = copy(root->_right);
return NewRoot;
}
~BSTree()
{
Destroy(_root);
_root = nullptr;
}
void Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
Node* Find(const K& key)
{
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 Insert(const K& key, const V& value)
{
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
if (parent->_key > key)
{
parent->_left = new Node(key, value);
}
else
{
parent->_right = new Node(key, value);
}
}
bool Erase(const K& key)
{
Node* cur = _root;
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//找到要删除的节点
{
//没有孩子或一个孩子
if (cur->_left == nullptr)
{
if (_root->_key == key)
{
_root = _root->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else if (parent->_right == cur)
{
parent->_right = cur->_right;
}
}
delete cur;
cur = nullptr;
return true;
}
else if (cur->_right == nullptr)
{
if (_root->_key == key)
{
_root = _root->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else if (parent->_right == cur)
{
parent->_right = cur->_left;
}
}
delete cur;
cur = nullptr;
return true;
}
//有两个孩子
else
{
//用要删除节点的右子树的最小节点代替删除节点
parent = cur;
Node* MinNode = cur->_right;
while (MinNode->_left)
{
parent = MinNode;
MinNode = MinNode->_left;
}
cur->_key = MinNode->_key;
if (parent->_left == MinNode)
{
parent->_left = MinNode->_right;
}
else
{
parent->_right = MinNode->_right;
}
delete MinNode;
return true;
}
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(const Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " " << root->_value << endl;
_InOrder(root->_right);
}
Node* _root = nullptr;
};
KV模型的二叉搜索树在查找、插入和删除操作上的性能通常取决于树的高度。在最坏的情况下(即树蜕化为单边树时),这些操作的时间复杂度会退化为O(n)。 可以使用平衡二叉搜索树来提高性能:
关于平衡二叉搜索树的介绍还请在我专栏 C++ 中查找相关文章。 在平均情况下,这些操作的时间复杂度可以接近O(log n),这使得KV模型的二叉搜索树成为一种高效的数据结构。
本篇文章的学习就到这了,如果您觉得在本文中有所收获,还请留下您的三连支持哦~