Immutable Map implementation using Red-Black Tree in Haxe

Map.hx

private enum Color { Red; Black; }

private enum TreeT<T> {
    Leaf;
    Node(color: Color, left: TreeT<T>, label: T, right: TreeT<T>);
}

private class TreeF {
    private function new() {}

    public static function balance<T>(tree: TreeT<T>): TreeT<T> {
        return switch (tree) {
        case  Node(Black, Node(Red, Node(Red, a, x, b), y, c), z, d)
            | Node(Black, Node(Red, a, x, Node(Red, b, y, c)), z, d)
            | Node(Black, a, x, Node(Red, Node(Red, b, y, c), z, d))
            | Node(Black, a, x, Node(Red, b, y, Node(Red, c, z, d))):
            Node(Red, Node(Black, a, x, b), y, Node(Black, c, z, d));
        case _:
            tree;
        }
    }
}

typedef MapT<K, V> = { tree: TreeT<{ key: K, value: V }>, comparator: K -> K -> Bool };

class Map {
    private function new() {}

    public static function create<K, V>(comparator: K -> K -> Bool): MapT<K, V> {
        return { tree: Leaf, comparator: comparator };
    }

    public static function insert<K, V>(map: MapT<K, V>, key: K, value: V): MapT<K, V> {
        function ins(tree: TreeT<{ key: K, value: V}>, comparator: K -> K -> Bool): TreeT<{ key: K, value: V}> {
            return switch (tree) {
            case Leaf: Node(Red, Leaf, { key: key, value: value }, Leaf);
            case Node(color, left, label, right):
                if (comparator(key, label.key))
                    TreeF.balance(Node(color, ins(left, comparator), label, right))
                else if (comparator(label.key, key))
                    TreeF.balance(Node(color, left, label, ins(right, comparator)))
                else
                    tree;
            }
        };

        return switch (ins(map.tree, map.comparator)) {
        case Leaf:
            throw "Never reach here";
        case Node(_, left, label, right):
            { tree: Node(Black, left, label, right), comparator: map.comparator };
        }
    }

    public static function find<K, V>(map: MapT<K, V>, key: K): Null<V> {
        function mem(tree: TreeT<{ key: K, value: V}>): Null<V> {
            return switch (tree) {
            case Leaf: null;
            case Node(_, left, label, right):
                if (map.comparator(key, label.key))
                    mem(left);
                else if (map.comparator(label.key, key))
                    mem(right);
                else
                    label.value;
            }
        }
        return mem(map.tree);
    }
}

Test.hx

using Map;

@:expose('Test')
class Test {
    public static function main(): Void {
        var m = Map.create(function (x, y) { return x < y; });
        for (i in 0...10000) {
            m = m.insert(i, i+1);
        }
        trace(m.find(1234));
    }
}