non-binary self balancing tree

Question

I'm looking for a tree data structure that allows to keep the tree balanced in high (minimum high as possible).

I mean, suppose a tree where:

• each node has a parameter k that is the maximum number of sons that can be attached to him, $0≤k≤N$

• all the operations will be about insert and delete (no search): it's just just important that every node know the son/s, I'm not interested at all in search (<0.1% of operations)

Would an adaption of RB-tree or AVL tree be a good idea for that task or there are better solutions (other data structures, other kind of tree, etc)?

Answer 1

You can use a binary prefix-trie (critbit-tree). It's not exactly selfbalancing, but it never requires rebalancing and imbalance is limited. For example, with 64bit keys, the maximum depth is strictly 64. This is not exactly the lowest possible height, but maybe that requirement can be relaxed because no rebalancing ever occurs?

You can find an (my) implementation here.

Answer 2

If your tree is a non-binary tree, and you have no limitations on the number of children, you can create a tree with a single root and infinite number of children. The height of that tree will be always 1.

class Node
{
    int data;
    SortedSet<int> children;
    function insert(int n)
    {
        children.add(n);
    }
    function delete(int n)
    {
        if(n exists in children) then delete n;
        else return error;
    }
}

Application:

Node root = new Node(5);
root.insert(8);
root.insert(10);
root.insert(20);
root.insert(-9);
root.insert(72);
root.insert(65);
root.delete(20);

The result will look like this:

             5
      /   /  |  \   \
   -9   8   10   65  72

Both insert() and delete() will take $O(\log (n-1)) = O(\log n)$ time in the worst case, $n$ being the number of nodes in the tree.