import RBTreeNode from './red-black-tree-node';
import * as utils from '../../utils';
/***************************************************************************************************
* A red-black tree is a binary tree that satisfies the red-black properties:

* 1. Every node is either red or black
* 2. The root is black
* 3. Every leaf (null) is black
* 4. If a node is red, both it's children are black
* 5. For all ndoes, all paths from the node to descendant leaves contain the same number of black nodes

* You might be wondering how did anyone come up with all these rules?

* Red-black trees are really just isometries of 2-3-4 trees. If you lift up the red nodes into their
* parents, the red-black tree becomes a 2-3-4 tree - a B-tree with branching factor 2.

* The complex rules of red-black trees make perfect sense if you connect it back to 2-3-4 trees.
* Since 2-3-4 trees support O(logn) insertions and deletions, so does the red-black tree.

* Dont memorize red/black rotations and color flips. If you're going to code up a red-black tree,
* just open up CLRS and translate the pseudocode.

* search() - O(logn)
* insert() - O(logn)
* remove() - O(logn)

* Implementation is based off CLRS, chapter 13.
**************************************************************************************************/
declare class RedBlackTree<T> {
    root: RBTreeNode<T> | null;
    private sz;
    private compare;
    constructor(compareFunction?: utils.CompareFunction<T>);
    /*****************************************************************************
                                    INSPECTION
    *****************************************************************************/
    size(): number;
    isEmpty(): boolean;
    height(): number;
    private heightHelper;
    /*****************************************************************************
                                    SEARCHING
    *****************************************************************************/
    find(value: T): RBTreeNode<T> | null;
    findMin(root?: RBTreeNode<T> | null): RBTreeNode<T> | null;
    findMax(root?: RBTreeNode<T> | null): RBTreeNode<T> | null;
    findSucessor(root: RBTreeNode<T>): RBTreeNode<T> | null;
    findPredecessor(root: RBTreeNode<T>): RBTreeNode<T> | null;
    /*****************************************************************************
                                    INSERTION/DELETION
    *****************************************************************************/
    insert(value: T): RBTreeNode<T>;
    insertFix(z: RBTreeNode<T>): void;
    remove(z: RBTreeNode<T>): boolean;
    private removeFix;
    private leftRotate;
    private rightRotate;
    private transplant;
    /*****************************************************************************
                                    READING
    *****************************************************************************/
    inorderTraversal(): {
        [Symbol.iterator](): Iterator<T>;
    };
    preorderTraversal(): {
        [Symbol.iterator](): Iterator<T>;
    };
    postorderTraversal(): {
        [Symbol.iterator](): Iterator<T>;
    };
}
export default RedBlackTree;
//# sourceMappingURL=index.d.ts.map