二叉搜索树

目录

一、 定义

二、 特性

三、c++实现二叉搜索树

3.1模拟实现

3.2详解删除

四、总结

一、 定义

二叉搜索树是一种特殊的二叉树，满足以下性质：

• 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
• 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
• 任意节点的左、右子树也分别为二叉搜索树。

二、 特性

• BST的平均检索时间复杂度为O(log n)，但在最坏情况下（树退化为链表）为O(n)。
• BST的插入和删除操作的时间复杂度同样为O(log n)。

三、c++实现二叉搜索树

3.1模拟实现

	template<class K>
	//struct BinarySearchTreeNode
	struct BSTreeNode
	{
		BSTreeNode<K>* _left;
		BSTreeNode<K>* _right;
		K _key;

		BSTreeNode(const K& key)
			:_left(nullptr)
			, _right(nullptr)
			, _key(key)
		{}
	};

	template<class K>
	class BSTree
	{
		typedef BSTreeNode<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->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}

			return true;
		}

		bool Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key < key)
				{
					cur = cur->_right;
				}
				else if (cur->_key > key)
				{
					cur = cur->_left;
				}
				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->_right;
				}
				else if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					// 删除
					// 左为空，父亲指向我的右
					if (cur->_left == nullptr)
					{
						//if(parent == nullptr)
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (cur == parent->_left)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}

						delete cur;
					}
					else if (cur->_right == nullptr)
					{
						//if(parent == nullptr)
						if (cur == _root)
						{
							_root = cur->_left;
						}
						else
						{
							// 右为空，父亲指向我的左
							if (cur == parent->_left)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}

						delete cur;
					}
					else
					{
						// 左右都不为空，替换法删除
						// 
						// 查找右子树的最左节点替代删除
						Node* rightMinParent = cur;
						Node* rightMin = cur->_right;
						while (rightMin->_left)
						{
							rightMinParent = rightMin;
							rightMin = rightMin->_left;
						}

						swap(cur->_key, rightMin->_key);

						if (rightMinParent->_left == rightMin)
							rightMinParent->_left = rightMin->_right;
						else
							rightMinParent->_right = rightMin->_right;

						delete rightMin;
					}

					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;
	};

3.2详解删除

删除操作相对复杂，需要分三种情况讨论：

• 待删除节点是叶子节点（无左右子节点）；

这个可以直接删除

• 待删除节点只有左子节点或只有右子节点；

待删除结点只有右子节点：

待删除结点只有左子节点：

                    if (cur->_left == nullptr)
					{
						//if(parent == nullptr)
						if (cur == _root)
						{
							_root = cur->_right;
						}
						else
						{
							if (cur == parent->_left)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}

						delete cur;
					}

• 待删除节点既有左子节点又有右子节点

  	// 左右都不为空，替换法删除			
	// 查找右子树的最左节点替代删除
    Node* rightMinParent = cur;
    Node* rightMin = cur->_right;
    while (rightMin->_left)
    {
	    rightMinParent = rightMin;
	    rightMin = rightMin->_left;
    }

    swap(cur->_key, rightMin->_key);
    if (rightMinParent->_left == rightMin)
    	rightMinParent->_left = rightMin->_right;
    else
	    rightMinParent->_right = rightMin->_right;

    delete rightMin;

四、总结

本文介绍了二叉搜索树的基本概念和C++实现方法，包括节点定义、插入、检索和删除操作。BST在数据检索中具有很高的效率，但需要注意的是，在最坏情况下（树退化为链表），BST的性能会大大降低。因此，在实际应用中，我们可能需要对BST进行平衡操作，以提高其性能。常见的平衡二叉搜索树有AVL树、红黑树等