二叉搜索树的概念
二叉搜索树又称二叉排序树,它或者是一颗空树,或者具有以下性质的二叉树:
- 若它的左子树不为空,则左子树上所有的节点的值都小于等于 根节点的值
- 若它的右子树不为空,则右子树上所有的节点的值都大于等于 根节点的值
- 它的左右子树也分别为二叉搜索树
- 二叉搜索树可以支持插入相同的值(multimap/multiset),也可以不支持插入相等的值(map/set)
二叉搜索树的性能分析
- 最优的情况:二叉搜索树为完全二叉树(或者接近完全二叉树),它的高度是:O(log2 N)
- 最坏的情况:二叉搜索树退化为单支树(类似于单支),它的高度是:O(N/2)
所以综合而言二叉搜索树增删改时间复杂度是:O(N)
但是这样的效率显然无法满足我们的需求,后续的博客我将介绍二叉搜索树的变形,平衡二叉树AVL树和红黑树,才能适用于我们在内存在存储和搜索数据。
二叉搜索树的插入
不用递归,采用更简单的循环
插入的具体步骤如下:
- 树为空,则直接新增节点,赋值给root指针
- 树不为空,按照二叉搜索树性质,插入值比当前节点大往右走,插入值比当前节点小往左走,找到空位置,插入新节点。
- 如果支持插入相同的值,插入值跟当前节点相等的值可以往右走,也可以往走左走,找到空位置,插入新节点(要注意保持逻辑的一致性,插入相同的值不要一会向右走,一会向左走)
二叉搜索树的查找
- 从根节点开始比较,查找x,x比根节点的值大则向右边走查找,x比根节点的值小则向左边走查找
- 最多查找高度次,走到空时,还没找到x,那么这个值在这个二叉搜索树中不存在
- 如果不支持插入相同的值,则找到x后可以直接返回
- 如果支持插入相同的值,则意味着可能存在多个x,一般要求查找中序的第一个x
二叉搜索树的删除
首先查找元素是否在二叉搜索树中,如果不存在,则返回false
如果查找元素存在则分为以下四个情况进行分别处理:(假设要删除的节点为N)(分类依据:孩子的个数)
- 要删除的节点N左右孩子均为空(即N为叶子节点)
- 要删除的节点N左孩子为空,右孩子不为空
- 要删除的节点N左孩子不为空,右孩子为空
- 要删除的节点N左右孩子均不为空
对于以上四种情况的解决办法:
- 把N节点的父亲对应孩子指针指向空,直接删除N节点(1可以和2.3一起处理)
- 把N节点的父亲对应孩子指针指向N的右孩子,直接删除N节点
- 把N节点的父亲对应孩子指针指向N的左孩子,直接删除N节点
- 无法直接删除N节点,因为N的两个孩子无处安放,只能采用替代法将其删除:将N左子树的最大值的节点R(最右节点)或者N右子树的最小值的节点R(最左节点)代替N,因为这两个节点中任意一个,放到N的节点,都满足二叉搜索树的规则。代替N的意思就是N和R的两个节点的值交换,转而变成删除R节点,R节点符合情况2或者情况3,可以直接删除
实现代码
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 Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}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{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;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){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{if (nullptr == cur->_left){if (parent == nullptr){_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else if (parent->_right = cur){parent->_right = cur->_right;}}delete cur;return true;}else if (nullptr == cur->_right){if (nullptr == parent){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;return true;}else{Node* leftMaxP = cur;Node* leftMax = cur->_left;while (leftMax->right){leftMaxP = leftMax;leftMax = leftMax->_right;}cur->_key = leftMax->_key;if (leftMaxP->_left == leftMax){leftMaxP->_left = leftMax->_left;}else{leftMaxP->_right = leftMax->_left;}delete leftMax;return true;}}}return false;}void InOrder(){_InOrder(_root);cout << endl;}
private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}private:Node* _root = nullptr;
};
二叉搜索树key和key/value使用场景
key搜索场景
只有key作为关键码,在二叉树结构中只需要存储key即可,搜索场景只需要判断key在不在。key的搜索场景支持二叉树的增删查,而不支持二叉树的修改,会破坏二叉树的结构。
key/value搜索场景
每一个关键码key,都有与它对应的值value,value可以是任何类型对象。树的结构中(每个节点)除了需要存储key,还需要存储value,增/删/查还是以key为关键字走二叉树的规则进行比较,可以快速找到与key对应的value。并且key/value的搜索场景支持了二叉树的修改,但是仍然不可以修改key,只可以修改value。
key/value二叉搜索树代码实现
template<class K, class V>struct BSTNode{K _key;V _value;BSTNode<K, V>* _left;BSTNode<K, V>* _right;BSTNode(const K& key, const K& 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>& m){_root = Copy(m._root);}BSTree<K, V>& operator=(BSTree<K, V> m){swap(_root, m._root);return *this;}~BSTree(){Destroy(_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){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->_right = cur;}else{parent->_left = cur;}return true;}Node* Find(const K& key){Node* 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){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{if (nullptr == cur->_left){if (nullptr == parent){_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;return true;}else if (nullptr == cur->_right){if (nullptr == parent){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;return true;}else{Node* rightMinP = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMinP->_left == rightMin){rightMinP->_left = rightMin->_right;}else{rightMinP->_right = rightMin->_right;}delete rightMin;return true;}}}return false;}void InOrder(){_InOrder(_root);cout << endl;}private:void _InOrder(Node* root){if (nullptr == root){return;}_InOrder(root->_left);cout << root->_key << ':' << root->_value << endl;_InOrder(root->right);}void Destroy(Node* root){if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;}Node* Copy(Node* root){if (nullptr == root){return nullptr;}Node* newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}private:Node* _root = nullptr;};