博客

1.应用场景：

二分搜索树解决的是查找类问题，在数据有序的基础上，二分搜索树的查找效率为O(logN)。

2.二分搜索树：

是一个二叉树，满足条件1.所有节点的值大于其左子节值点小于其右子节点值；2.所有节点的值大于其左子树所有节点值，小于右子树所有节点值。

3.算法实现：

下面代码实现了二分搜索树的插入，删除，遍历（前序、中序、后续、广度优先），查找等操作

/************************************************************************/
/* 二分搜索树：是一个二叉树。每个节点的值大于其左子树的所有值，小于其右子树的所有值                                                                     */
/************************************************************************/

template<typename Key,typename Value>
class BinarySearchTree
{

private:

	struct Node{
		Key key;
		Value value;
		Node* left;
		Node* right;

		Node(Key key,Value value)
		{
			this->key = key;
			this->value = value;
			this->right=this->left=NULL;
		}

		Node(Node* node)
		{
			this->key = node->key;
			this->value = node->value;
			this->left = node->left;
			this->right = node->right;
		}
	};

	///根节点
	Node* root;	

	///节点个数
	int count;

public:

	BinarySearchTree()
	{
		root = NULL;
		count = 0;
	}

	~BinarySearchTree()
	{
		///释放节点，要求先删除子节点，最后释放自身节点，因此使用后序遍历
		destory(root);
	}

	//插入元素
	void inser(Key key,Value value)
	{
		insert(root,key,value);
	}

	//查找是否包含指定元素
	bool contain(Key key)
	{
		return contain(root,key);
	}

	//搜索键对应的值，如果不存在返回null
	Value* search(Key key)
	{
		return search(root,key);
	}

	//前序遍历
	void preOrder()
	{
		preOrder(root);
	}

	//中序遍历
	void inOrder()
	{
		inOrder(root);
	}

	//后序遍历
	void postOrder()
	{
		postOrder(root);
	}

	//层序遍历，深度小的节点先遍历
	void levelOrder()
	{
		if(!root)
			return ;

		queue<Node*> nodeQueue;	//先入先出
		nodeQueue.push(root);
		while(!nodeQueue.empty())
		{
			//每次弹栈将其子节点存入,使得深度相同的节点在队列中总是相邻
			Node* node = nodeQueue.front();
			nodeQueue.pop();
			std::cout<<node->value<<std::endl;
			
			if(node->left)
				nodeQueue->push(node->left);
			if(node->right)
				nodeQueue->push(node->right);
		}
	}

	///寻找树中最小键值
	Key minium()
	{
		Node* minNode = minium(root);
		return minNode->key;
	}

	///寻找树中最大键值
	Key maximum()
	{
		Node* maxNode = maximum(root);
		return maxNode->key;
	}

	//删除最小节点
	void removeMin()
	{
		if(root)
			root = removeMin(root);
	}

	///删除节点
	void remove(Key key)
	{
		root = remove(root,key);
	}



private:

	Node* insert(Node* node,Key key,Value value)
	{
		if(node == NULL){
			count ++;
			return new Node(key,value);
		}

		if(node->key==key)
			node->value = value;
		else if(node->key>key)
			node->left = insert(node->left,key,value);
		else
			node->right = insert(node->right,key,value)
	}

	bool contain(Node* node,Key key)
	{
		if(node == NULL)
			return false;

		if(node->key==key)
			return true;
		else if(node->key>key)
			return contain(node->left,key);
		else
			return contain(node->right,key)
	}

	Value* search(Node* node,Key key)	///时间复杂度为O(logn)
	{
		if(!node)
			return NULL;
		if(node->key == key)
			return &(node->value);
		else if(node->key>key)
			return search(node->left,key);
		else 
			return search(node->right,key);
	}

	void preOrder(Node * node)
	{
		if(node==nullptr)
			return ;
		std::cout<<node->value<<std::endl;
		preOrder(node->left);
		preOrder(node->right);
	}

	void inOrder(Node* node)
	{
		if(node==nullptr)
			return ;
		inOrder(node->left);
		std::cout<<node->value<<std::endl;
		inOrder(node->right);
	}

	void postOrder(Node* node)
	{
		if(node==nullptr)
			return ;
		postOrder(node->left);
		postOrder(node->right);
		std::cout<<node->value<<std::endl;
	}

	void destory(Node* node)
	{
		if(node)
		{
			destory(node->left);
			destory(node->right);
			delete node;
			node = NULL;
			count--;
		}
	}

	//最小节点即树中最靠左的节点
	Node* minium(Node* node)
	{
		if(node->left==NULL)
		{
			return node;
		}
		return minium(node->left);
	}

	//最大节点即树中最靠右的节点
	Node* maxium(Node* node)
	{
		if(node->right==NULL)
		{
			return node;
		}
		return maxium(node->right);
	}

	//删除最小节点
	Node* removeMin(Node* node)
	{
		if(node->left == NULL)
		{
			Node* rightNode = node->right;
			delete node;
			count--;
			return rightNode;	//无论最小节点的右节点是否为空，都应该使用右节点替换原最小节点（因为右节点为空的话原最小节点的父节点的左子节点本身就应该设置空）
		}
		node->left = removeMin(node->left);
		return node;
	}

	//删除最大节点
	Node* removeMax(Node* node)
	{
		if(node->right == NULL)
		{
			Node* leftNode = node->left;
			delete node;
			count--;
			return leftNode;
		}
		node->right = removeMax(node->right);
		return node;
	}

	///删除节点
	Node* remove(Node* node,Key key)
	{
		if(node == NULL)	//当前树中不存在键值为key的节点
			return NULL ;
		if(node->key > key)	//小于当前节点键值，使用左子树进行查找
		{
			node->left = remove(node->left,key);
			return node;
		}else if(node->key < key)	//大于当前节点键值，使用右子树进行查找
		{
			node->right = remove(node->right.key,key);
			return node;
		}else{	//匹配到key所对应的节点
			if(node->left == NULL)	///左节点为空，使用右子节点替换原父亲节点
			{
				Node rightNode = node->right;
				delete node;
				count--;
				return rightNode;
			}
			if(node->right == NULL)	///右节点为空，使用左子节点替换原父亲节点
			{
				Node* leftNode = node->left;
				delete node;
				count--;
				return leftNode;
			}
			///左右节点皆不为空，删除当前节点，使用右子树中的最小节点替换当前节点
			Node* minNode = new Node(minium(node->right));	//返回的最小节点在下一步中已经被删除,所以要复制一份
			count++;
			minNode->left = node->left;
			minNode->right = removeMin(node->right);	//节点计数-1
			
			delete node;
			count--;	//节点计数-1
			return minNode;
		}
	}
};

4.基于二分搜索树的应用拓展

除了查找之外，二分搜索树具有顺序性，可以解决和元素顺序相关的一系列问题。比如：最大最小值（最左/右的叶子节点），元素的前驱（左子树的最大节点）和后继（右子树的最小节点），在节点中增加字段以当前节点为根节点的二叉树的节点个数可以解决select（索引？的元素是i）和rank问题（元素i的索引是？）

5.二分搜索树的局限性

当插入的数据本身有序且按顺序进行插入时，二分搜索树退化成了一个链表，所有操作都变成了O(N)级别，解决方案是使用平衡二叉树