/**
 * 相关性质:
 * 1: 结点是红色或黑色
 * 2: 根结点是黑色
 * 3: 所有叶子都是黑色（叶子是null结点）
 * 4: 每个红色结点的两个子结点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色结点）
 * 5: 从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点
 *
 * 性质1和性质3总是保持着。
 * 性质4只在增加红色节点、重绘黑色节点为红色，或做旋转时受到威胁。
 * 性质5只在增加黑色节点、重绘红色节点为黑色，或做旋转时受到威胁。
 */
declare class RBTree<K, V> {
    /**
     * 有类继承当前类的话
     * new 时会调用当前的构造函数
     */
    static get [Symbol.species](): typeof RBTree;
    /**
     * 根节点
     */
    private root;
    /**
     * 最小值
     */
    private minimum;
    /**
     * 最大值
     */
    private maximum;
    /**
     * 节点数
     */
    private nodeSize;
    /**
     * 比较器
     */
    private comparator;
    /**
     * 不带数据的初始化
     * 因为插入操作需要考虑相同key时怎么操作
     */
    constructor(comparator: (lhs: K, rhs: K) => number);
    /**
     * 节点个数
     */
    getSize(): number;
    getMin(): V;
    getMax(): V;
    /**
     * 是否为空树
     */
    isEmpty(): boolean;
    /**
     * 插入节点
     * @description 允许有节点有相同的key
     */
    insertMultiple(key: K, value: V): void;
    /**
     * 插入节点
     * @description 不允许有相同的key,有则忽略插入节点
     */
    insertUnique(key: K, value: V): void;
    /**
     * 插入节点
     * @description 有相同节点的，直接替换为新节点
     */
    insertOrReplace(key: K, value: V): void;
    /**
     * 移除节点
     * @description 如果有两个子节点,找左子树的最大值或右字树的最小值，移动对应值，颜色不改动
     */
    remove(key: K): void;
    /**
     * 清空红黑树
     */
    clear(): void;
    has(key: K): boolean;
    getValue(key: K): V;
    /**
     * 先序遍历二叉树
     */
    forEach(callback: (value: V, key: K) => void): void;
    keys(): {
        next: () => {
            value: K;
            done: boolean;
        };
    };
    values(): {
        next: () => {
            value: V;
            done: boolean;
        };
    };
    entries(): {
        next: () => {
            value: [K, V];
            done: boolean;
        };
    };
    toString(): string;
    /**
     * ES6 迭代器
     */
    [Symbol.iterator](): {
        next: () => {
            value: [K, V];
            done: boolean;
        };
    };
    /**
     * @description Object.prototypt.toString.call(RBTree) 时返回 '[object RBTree]'
     */
    get [Symbol.toStringTag](): string;
    /**
     * 节点比较
     */
    private compareNode;
    /**
     * 判断是不是叶节点
     * @description 叶节点是null
     */
    private isLeaf;
    /**
     * 是否是根节点
     */
    private isRoot;
    /**
     * 替换节点,旋转时会用到
     * @description 修改节点的父节点及父节点对应的子节点
     */
    private replaceNode;
    /**
     * ===================
     *      节点旋转
     * ===================
     *
     *     X                Y
     *    / \              / \
     *   Y   c  右旋 -->  a   X
     *  / \     <-- 左旋     / \
     * a   b                b   c
     */
    /**
     * 左旋
     * @param node - 参考Y节点
     */
    private rotateLeft;
    /**
     * 右旋
     * @param node - 参考X节点
     */
    private rotateRight;
    /**
     * 获取节点颜色
     */
    private fetchColor;
    /**
     * 判断节点颜色
     */
    private isBlack;
    /**
     * 判断节点颜色
     */
    private isRed;
    /**
     * 插入节点，处理相关变更
     */
    private insert;
    private insertNode;
    /**
     * 开始插入操作的修复
     * 文档可能会不一样，因为英文版的文档已经完全不同了
     * {@link https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91#%E6%8F%92%E5%85%A5 插入操作说明}
     */
    private insertRepairTree;
    /**
     * 情况1: 插入的节点是根节点
     * 直接把该节点颜色改成黑色就行
     */
    private repairCase1;
    /**
     * 情况2: 新节点的父节点是黑色
     * 不需要做任何处理
     */
    private repairCase2;
    /**
     * 情形3: 父节点和叔父节点二者都是红色
     */
    private repairCase3;
    /**
     * 情形4: 父节点P是红色而叔父节点U是黑色或缺少
     *        并且新节点是其父节点的右子节点而父节点又是其父节点的左子节点
     */
    private repairCase4;
    /**
     * 情况5: 父节点P是红色而叔父节点U是黑色
     * 情形4 完成之后一定为情形5
     */
    private repaireCase5;
    /**
     * 根据 key 查对应的节点
     */
    private getNodeByKey;
    /**
     * @description 获取相对于当前节点的最大值
     */
    private getMaxNode;
    /**
     * 转换被删除的节点
     * @description 如果当前节点有两个子节点，转换成最多有一个子节点的节点
     */
    private convertDeleteNode;
    /**
     * 删除节点
     * @description 需要确保节点存在
     */
    private removeNode;
    /**
     * 情况1: node 是新的根
     */
    private eraseCase1;
    /**
     * 情况2: 兄弟节点是红色
     */
    private eraseCase2;
    /**
     * 情况3: 当前节点的父节点、兄弟节点和兄弟的儿子都是黑色的
     */
    private eraseCase3;
    /**
     * 情形4: 兄弟节点和兄弟的儿子节点都是黑色，但是父节点是红色
     */
    private eraseCase4;
    /**
     * 情形5: 兄弟节点是黑色
     * 兄弟节点的左儿子节点是红色
     * 兄弟节点的右儿子节点是黑色
     * 而当前节点是它父亲的左儿子节点
     */
    private eraseCase5;
    /**
     * 情形6: 兄弟节点是黑色
     * 兄弟的右儿子节点是红色
     * 当前节点是它父亲的左儿子节点
     */
    private eraseCase6;
    /**
     * 迭代器方法会用到
     * @description 获取正向遍历的下一个节点
     */
    private next;
    /**
     * @description 获取以当前节点为根节点的最小值
     */
    private getMinNodeByNode;
    /**
     * 生成迭代器
     */
    private getIterator;
}
export default RBTree;