二查搜索树（Java）

/*****************搜索二叉树*********************/
//《算法导论》P161
	/*构建一个有n个不同关键字的二查搜索树的期望高度为h = O(lgn);
	  下述所有查找等操作的时间复杂度为O(h)
	*/

	/******定义搜索二叉树*****/
//对于任一节点x，满足其左子树上的节点key都不大于x.key
//	                   右子树上的节点key都不小于x.key
	private class SearchTree
	{
		int key;
		SearchTree parent;
		SearchTree left;
		SearchTree right;
	}

	/*********************查询*********************/
	//递归实现
	public SearchTree Search1(SearchTree TNode , int target)
	{
		if(TNode == null || target == TNode.key)
		{
			return TNode;
		}
		
		if(target > TNode.key)
		{
			return Search(TNode.right,target);//递归查询右子树
		}
		else
		{
			return Search(TNode.left,target);
		}
	}

	//迭代实现(效率相对要高的多)
	public SearchTree Search(SearchTree TNode,int target)
	{
		while(TNode != null && target != TNode.key)
		{
			if(target > TNode.key)
			{
				TNode = TNode.right;
			}
			else
			{
				TNode = TNode.left;
			}
		}
		return TNode;
	}

	/******************查询最大最小关键字***************/
	//最小关键字
	public SearchTree MinTreeNode(SearchTree TNode)
	{
		while(TNode.left != null)
		{
			TNode = TNode.left;
		}
		return TNode;
	}

	//最小关键字
	public SearchTree MaxTreeNode(SearchTree TNode)
	{
		while(TNode.right != null)
		{
			TNode = TNode.right;
		}
		return TNode;
	}

	/*****************查找后继和前驱******************/
	/*
	查找一个节点的后继
	*/
	/*注意要分为两种情况：1.若该节点有右节点，则后继为其右节点的最左节点
	                      2.若该节点无右子树，则应该回溯到期祖宗节点进行考虑
						    1）若节点为其父节点x.p的左子节点,则x.key小于x.p.key
	                        2）若节点为父节点的右子节点，查找大于其key的后继依然
							   无法满足；故仍向上追溯直至某一节点z，使得x在其z左子树中。						  
	*/

	public SearchTree TreeSuccessor(SearchTree XNode)
	{
		if(XNode.right != null)
		{
			return MinTreeNode(XNode.right);//即查找右子树的最小关键字
		}
		
		SearchTree YNode = XNode.parent;
		while(YNode != null && XNode == YNode.right)//循环至根节点之前的NIL或者该节点为父节点的左子节点
		{
			XNode = YNode;
			YNode = YNode.parent;
		}
		
		return YNode;//注意返回值
	}

	/*
	  查找一个节点的前驱
	*/
	/*类比于查找前驱的问题，1.当该节点有左子树，则前驱即为其左子树的最大关键字
	                        2.若该节点只有右子树，则返回其祖宗节点考虑
							  直至找到该节点x为z的右子树中的节点，则z为x的前驱
	*/

	public SearchTree TreePreDecessor(SearchTree XNode)
	{
		if(XNode.left != null)
		{
			return MaxTreeNode(XNode.left);
		}
		
		SearchTree YNode = XNode.parent;
		while(YNode != null && XNode == YNode.left)
		{
			XNode = YNode;
			YNode = YNode.left;
		}
		return YNode;
	}


	/*********************插入节点**********************/
	/*注意搜索二叉树的特点，插入的节点最后一定成为了二叉树的叶子节点
	  通过不断比较x.key与节点y的key,确定节点x应该在y的左子树还是右子树
	  同时处理二叉树要时常注意根节点的特殊性，进行考虑
	*/
	public void TreeInsert(SearchTree TRoot, SearchTree XNode)
	{
		SearchTree YNode = null;
		while(TRoot != null)
		{
			YNode = TRoot;//避免退出循环时TRoot为null，而无法进行访问
			if(XNode.key > TRoot.key)
			{
				TRoot = TRoot.right;
			}
			else
			{
				TRoot = TRoot.left;
			}
		}
		XNode.parent = YNode;
		//注意根节点情况
		if(YNode == null)//即TRoot=null,未进入循环
		{
			TRoot = XNode;
		}
		//要判断XNode是左节点还是右节点
		else if(XNode.key < YNode.key)
		{
			YNode.left = XNode; 
		}
		else
		{
			YNode.right = XNode;
		}
		
	}

	/*********************删除节点*********************/
	/*删除要考虑三种情况：（暂不考虑XNode不在树中的情况）
		1.XNode为叶子节点，没有子孩子，则将其删除，并将其父节点对应孩子节点置为null即可
		2.XNode有一个孩子节点YNode，无论是左右孩子，将YNode替代XNode即可
		3.XNode有两个孩子节点时，要分为如下两种情况
			1）XNode右孩子节点YNode无左子树           2）YNode有左子树:
	                   （x）                                 （x）
	                   /  \				                    /    	                  ()  (y)                              ()    (y)
					     /  \                                   /  	                    NIL ()                                 (m)   
	          直接让YNode取代XNode即可					         	                                                             (n)
			                                           注意要查找XNode的后继MNode,即右子树的最左节点，
													   让后让MNode替代XNode，并注意让MNode的右子树替代MNode
	*/   

	//替代辅助函数,注意这里面的替代仅是将VNode交换到UNode的位置，UNode本身并未作改变，后继也未继承
	private void Transplant(SearchTree TRoot, SearchTree UNode, SearchTree VNode)
	{
		//考虑根节点的情况
		if(UNode.parent == null)
		{
			TRoot = VNode;
		}
		else if(UNode == UNode.parent.left)
		{
			UNode.parent.left = VNode;
		}
		else
		{
			UNode.parent.right = VNode;
		}
		if(VNode != null) //注意此条件判断，null是无法设置各种状态的
		{
			VNode.parent = UNode.parent;
		}
	} 

	/**********************删除函数************************/
	public void TreeDelete(SearchTree TRoot, SearchTree XNode)
	{
		//情况一
		if(XNode.left == null && XNode.right == null)
		{
			XNode = null;//省去判断XNode是否为根节点
		}
		//情况二
		else if(XNode.left != null)
		{
			Transplant(TRoot,XNode,XNode.left);
		}
		else if(XNode.right != null)
		{
			Transplant(TRoot,XNode,XNode.right);
		}
		//情况三
		else
		{
			SearchTree YNode = XNode.right;
			//情况3.1
	        if(YNode.left == null)
			{
				Transplant(TRoot,XNode,YNode);
				//交换之后注意设置子孩子
				YNode.left = XNode.left;
				YNode.left.parent = YNode;
			}
			//情况3.2
			else
			{
				SearchTree MNode = MinTreeNode(YNode);
				Transplant(TRoot,MNode,MNode.right);//用NNode替换MNode
				//注意MNode发生改变
				MNode.right = XNode.right;
				MNode.right.parent = MNode;//要注意设置XNode孩子的节点的parent
				Transplant(TRoot,XNode,MNode);
				MNode.left = XNode.left;
				MNode.left.parent = MNode;
			}
		}
	}