package Tree;
/**
 * @author HuiJixu
 * @version 2.0
 * @since 2021.9
 */
public class BST<Key extends Comparable<Key> ,Value>{
    //BST's root  node
    private Node root;
	//定义节点的结构
    private class Node{
        private  Key key ;
        private Value value ;
        private Node left ,right ;   //指向该节点的子树的左右链接
        private int N ;            //该接待你所包含的节点数目
		//节点构造器
        public Node(Key key , Value value , int  N){
            this.key = key ;
            this.value = value ;
            this.N = N;
        }
        public int size(){return size(root) ;}
        public int size(Node x ){
            if (x == null){
                return  0 ;
            }else{
                return x.N;
            }
        }
        //按键索值
        //这个方法是暴露给用例的方法
        public Value get(Key key){
            return get(root , key);
        }
        //像这种不暴露给用例的方法就要做个封装
        private Value get(Node node, Key key){
            //在以root为根节点的树中查找并返回key对应的值，没有就null
            if (node == null )  return null ;
            //不为空就比较，类似二分法查找
            int temp = key.compareTo(node.key);
            if ( temp < 0 ) return  get(node.left,key);   //将当前节点的左子节点作为新根节点继续往下查找
            else if( temp > 0 ) return get(right.right,key); //将右子树根节点作为新根节点
            else return node.value;
        }
        public void put(Key key , Value value){
            //先查找key，有key则更新，没有就新建节点
            root = put( root , key ,value );
        }
		private Node put(Node node, Key key , Value value ){
            //找不到key说明是新键，那就new 并插入该子树中
            if(node == null) return  new Node(key,value,1) ; //最新的叶子节点只含所有自己一个节点
            //key存在在以当前node为根节点的子树中，就更新它的值
            int temp = key.compareTo(node.key);
            if( temp < 0 ) node.left = put(node.left ,key ,value );
            else if( temp > 0 ) node.right = put(node.right ,key , value ) ;
            else node.value = value ;
            //更新所含有的节点数目
            node.N = size(node.left) + size(node.right) + 1 ;
            return node;
        }
		//delete() 单独说这个方法先把代码放在这里
		public void delete(Key key){
            root = delete(root ,key);
        }
        //在delete操作中，要找出右子树中的最小键对应的value ,并将其作为新的根节点，而作为原先地方的节点就要珊瑚了
        public void deleteMin(){
            root = deleteMin(root);
        }
        public Node deleteMin(Node node){
            //不断检索左子树，直到遇见空节点，则说明该节点就位最小的
            if ( node.left == null) return node.right;
            //不是空的话就继续递归查找左子树
            node.left = deleteMin(node.left);
            //更新节点
            node.N = size(node.right)+ size(node.left) + 1 ;
            return  node;
        }
        private Node delete(Node node , Key key ){
            //空的就直接返回
            if (node == null) return  null ;
            //二分查找非空 .递归查找
            int temp = key.compareTo(node.key);
            if( temp < 0 ) node.left = delete(node.left , key);
            else if( temp > 0 ) node.right = delete(node , key);
            //找到了就删除
            else {
                //下一个是空的返回另一边
                if( node.left == null) return node.right ;
                else if ( node.right == null) return node.right ;
                //两边都不为空
                Node t = node ;   // 保存指向即将被删除的节点的链接
                t = min(node.right);  //将该链接重新指向要被删除的节点的后继节点（下文解释后继节点）
                node.right = deleteMin(t.right); //将要被删除的节点指向删除后仍然所有节点都大于node.key的													//子二叉树，保证树的有序性不变
                node.left = t.left ;  // 左链接保持一致
            }
            //更新删除后节点所含有子节点数
            node.N = size(node.left) + size(node.right) + 1 ;
            return  node ;
        }
        //返回最小值的节点的键
//        其实这样的话如果root节点过高的话，查询效率会首先与树的深度
        public Key min(){
            return min(root).key;
        }
        private Node min(Node node){
            if (node.left == null) return  node ;
            return min(node.left) ;
        }
    }
}