const Compare = {
    LESS_THAN: -1,
    BIGGER_THAN: 1,
    EQUALS: 0
};
function defaultCompare(a,b){
    return a == b?Compare.EQUALS:(a<b)?Compare.LESS_THAN:Compare.BIGGER_THAN;
}
class Node{
    constructor(key){
        this.key = key;
        this.left = null;
        this.right = null;
    }
}
class BinarySearchTree{
    constructor(compareFn = defaultCompare){
        this.compareFn = compareFn;
        this.root = null;
    }
    insert(key){
        if(this.root == null){
            this.root = new Node(key);
        }else{
            this.insertNode(this.root,key);
        }
    }
    insertNode(node,key){
        if(this.compareFn(key,node.key)===Compare.LESS_THAN){
            if(node.left == null){
                node.left = new Node(key);
            }else{
                this.insertNode(node.left,key);
            }
        }else{
            if(node.right == null){
                node.right = new Node(key);
            }else{
                this.insertNode(node.right,key);
            }
        }
    }
    inOrderTraverse(callback){//callback是回调函数，在这里当作参数
        this.inOrderTraverseNode(this.root,callback);
    }
    inOrderTraverseNode(node,callback){
        if(node == null)return;
        this.inOrderTraverseNode(node.left,callback);
        callback(node.key);
        this.inOrderTraverseNode(node.right,callback); 
    }
    preOrderTraverse(callback){
        this.preOrderTraverseNode(this.root,callback);
    }
    preOrderTraverseNode(node,callback){
        if(node == null) return;
        callback(node.key);
        this.preOrderTraverseNode(node.left,callback);
        this.preOrderTraverseNode(node.right,callback);
    }
    postOrderTraverse(callback){
        this.postOrderTraverseNode(this.root,callback);
    }
    postOrderTraverseNode(node,callback){
        if(node == null) return;
        this.postOrderTraverseNode(node.left,callback);
        this.postOrderTraverseNode(node.right,callback);
        callback(node.key);
    }
    min(){
        return this.minNode(this.root);
    }
    minNode(node){
        let current =node;
        while(current != null && current.left != null){
            current = current.left;
        }
        return current;
    }
    max(){
        return this.maxNode(this.root);
    }
    maxNode(node){
        let current = node;
        while(current != null && current.right != null){
            current = current.right;
        }
        return current;
    }
    search(key){
        return this.searchNode(this.root,key);
    }
    searchNode(node,key){
        if(node == null){
            return false;
        }
        if(this.compareFn(key,node.key) === Compare.LESS_THAN){
            return this.searchNode(node.left,key);
        }else if(this.compareFn(key,node.key) === Compare.BIGGER_THAN){
            return this.searchNode(node.right,key);
        }else{
            return true;
        }
    }
    remove(key){
        return this.removeNode(this.root,key);
    }
    removeNode(node,key){
        if(node == null){
            return null;
        }
        if(this.compareFn(key,node.key) === Compare.LESS_THAN){
            //删除之后，我要把更改后的情况返回给它的父节点
            node.left = this.removeNode(node.left,key);
            return node;
        }else if(this.compareFn(key,node.key) === Compare.BIGGER_THAN){
            node.right = this.removeNode(node.right,key);
            return node;
        }else{
            //第一种情况，节点没有子节点
            if(node.left == null && node.right == null){
                node = null;
                return node;//因为还有个父节点指向它，所以需要将返回null给父节点的指针，让父节点的指针为null；
            }
            //第二种情况，节点只有一个子节点
            if(node.left == null){
                node = node.left;
                return node;
            }else if(node.right == null){
                node = node.right;
                return node;
            }
            let aux = this.minNode(node.right);
            node.key = aux.key;
            //更新节点右边删除后的情况，并重新赋值。
            node.right = this.removeNode(node.right,aux.key);
            return node;
        }
    }
}