package com.wang.BST;

public class BST<Key extends Comparable<Key>, Value>
{
	private Node root;//根节点
	
	private class Node
	{
		private Key key;//节点的键
		private Value val;//节点的值
		private Node left,right;//节点指向的左右子树的链接
		private int N;//以该节点为根的子树中的节点总数
		
		public Node(Key key,Value val,int N)
		{
			this.key=key;
			this.val=val;
			this.N=N;
		}
	}
	
	public int size() //此为返回以该节点为根的子树中的节点总数
	{
		return size(root);
	}
	
	private int size(Node x)
	{	
		if(x==null)
			return 0;//空链表则表示节点数为零
		else
			return x.N;
	}
	
	//查找之用
	public Value get(Key key)
	{
		return get(root,key);
	}
	public Value get(Node x,Key key)
	{
		if(x==null)
			return null;//表示未找到，返回null
		int cmp=key.compareTo(x.key);//把要找的数和x结点代表的键进行比较
		if(cmp<0)
			return get(x.left,key);//小则找左子树
		else if(cmp>0)
			return get(x.right,key);
		else
			return x.val;//找到返回值
	}
	
	//插入节点
	public void put(Key key,Value val)
	{
		root=put(root, key, val);
	}
	//在返回的时候，返回的是下一级的值，但x之类是这一级所保存的
	private Node put(Node x,Key key,Value val)
	{
		if(x==null)              //没有插入的点就创建一个
			return new Node(key,val,1);
		int cmp = key.compareTo(x.key);
		if(cmp<0)
			x.left=put(x.left, key, val);
		else if(cmp>0)
			x.right = put(x.right,key,val);
		else                     //有插入的点就更新
			x.val=val;
		x.N=size(x.left)+size(x.right)+1;
		return x;
	}
	
	//返回二叉树中最小值
	public Key min()
	{
		return min(root).key;
	}
	private Node min(Node x)
	{
		if(x.left==null)
			return x;
		return min(x.left);
	}
	
	//返回最大值
	public Key max()
	{
		return max(root).key;
	}
	private Node max(Node x)
	{
		if(x==null)
			return x;
		return max(x.right);
	}
	
	public Key floor(Key key)
	{
		Node x=floor(root,key);
		if(x==null)
			return null;
		return x.key;
	}
	private Node floor(Node x,Key key)
	{
		if(x==null)
			return null;
		int cmp=key.compareTo(x.key);
		if(cmp==0)
			return x;
		if(cmp<0)
			return floor(x.left,key);
		Node t =floor(x.right,key);
		if(t!=null)
			return t;
		else
			return x;
	}
	
/*
  在deleteMin(Node x)方法之中，会进行递归运算，一直找到一个没有左子树的结点（就是要删除的点），之后会返回这个结点的右子树
　然后让这个删除节点的上一级的结点指向返回的右子树；之后会依次的递归返回，最终返回的是修改后的树的根节点；返回的时候对N进行修改
*/

	//删除最小键节点
	public void deleteMin()
	{
		root=deleteMin(root);//返还的是树的根
	}
	private Node deleteMin(Node x)
	{
		if(x.left==null)
			return x.right;//无左则返回有节点
		x.left=deleteMin(x.left);//当返还右节点时，使这个一个节点指向返回的右节点导致，下节点被删除
		x.N=size(x.left)+size(x.right)+1;
		return x;
	}
	

	public void delete(Key key)
	{
		root = delete(root,key);
	}

/*
情况1、如果没有找到要删的结点，返回null
情况2、如果匹配到了结点，则又分为三种情况
　　　　a、如果匹配的结点右子树为空则返回左子树
　　　　b、如果匹配的结点左子书为空则返回右子树
　　　　c、如果都不为空
　　　　　　　　则1、首先用t保存要删除的结点x
　　　　　　　　　2、从t（即要删除的结点）的右子树中找出最小的结点，让他替换x
　　　　　　　　　3、让更新之后的结点的右指针指向删除t的右子树的最小结点，调整之后的树的根节点
之后让修改之后的想x左子树与t的左子树相同 之后返回修改之后的x结点，依次递归返回
*/

	private Node delete(Node x,Key key)
	{
		if(x==null)  //不存在则反空
			return null;
		int cmp = key.compareTo(x.key); //比较键
		if(cmp<0)
			x.left=delete(x.left, key);
		else if(cmp>0)
			x.right=delete(x.right,key);
		else
		{
			//凡是到那个找到匹配节点，且左或者右子节点为空的，直接让上一级的节点指向即可
			if(x.right==null)
				return x.left;
			if(x.left==null)
				return x.right;
			Node t=x;
			x=min(t.right);
			x.right=deleteMin(t.right);
			x.left=t.left;
		}
		x.N=size(x.left)+size(x.right)+1;
		return x;
	}
}        

　　1、以链表的形式表示每一个结点；

　　　　 private Key key;//节点的键
　　　　 private Value val;//节点的值
　　　　 private Node left,right;//节点指向的左右子树的链接
	private int N;//以该节点为根的子树中的节点总数
  2、size()这个方法是用来计算某一结点为根时，根和子树一共的节点数（N）
  3、deleteMin()是为了删除树中的最小结点