0
$\begingroup$

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)?

|cite|improve this question
$\endgroup$
  • 4
    $\begingroup$ What's wrong with the variants listed on Wikipedia? What are your exact requirements? Also, if you never search what on earth do you keep these data for? $\endgroup$ – Raphael♦ Nov 23 '15 at 19:16
  • 3
    $\begingroup$ By the way: do I infer correctly that you need/want a sorted dictionary/set implementation? I know of none for which search is more expensive than insertion or deletion, since they typically have to perform a search before doing either. So as long as you have deletes, I'm not aware of any answer beyond the classical answers (and their numerous variants). $\endgroup$ – Raphael♦ Nov 23 '15 at 22:18
  • $\begingroup$ I would not use the expression "self balancing" for RB and AVL trees. These data structures have a forced balanced structure. In self balancing structures the balance is not forced but should follow from searches (and other operations). Think splay trees. $\endgroup$ – Hendrik Jan Nov 23 '15 at 23:13
  • 2
    $\begingroup$ In addition to the other helpful feedback, what does "balanced in high" mean? How do you plan to evaluate answers? Right now it looks like there are many possible answers, all equally valid. What do you mean by "better"? Better in what respect? Do you have performance requirements? Please edit the question to clarify all of these points. $\endgroup$ – D.W.♦ Nov 24 '15 at 0:24
  • $\begingroup$ If you see no way to improve your question, you can always post a self-answer with what you determined concludes your line of questioning. $\endgroup$ – Raphael♦ Nov 24 '15 at 13:19
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ i've expressed bad the first condition $\endgroup$ – abc Nov 24 '15 at 6:43
  • $\begingroup$ You have just reinvented the linear list, congratulations! And no, you don't get logarithmic operation time unless you use a worst-case logarithmic-cost SortedSet implementation, which is a catch-22. (Also, you have not improved on usual balanced search trees at all.) $\endgroup$ – Raphael♦ Nov 24 '15 at 8:30
  • $\begingroup$ @Raphael I am well aware it looks silly but that was what OP asked for :) I will edit it in a minute $\endgroup$ – padawan Nov 24 '15 at 9:38
  • $\begingroup$ @Raphael, I think that Java's SortedSet implementation uses a balanced binary tree scheme with $O(\log n)$ insert and delete, so it's not just a linked list. I see this as an answer that meets all of the requirements and isn't a catch-22. $\endgroup$ – D.W.♦ Nov 25 '15 at 21:07
  • $\begingroup$ We can distinguish the tree that @newbie wants to store, vs the data structure that cagirici uses for storing child lists: the former is not a binary tree, even if the latter is. So I see cagirici's answer as a clever (though possibly somewhat obvious) trick. As newbie notes, we can't just use a red-black tree to store the former tree as that tree is non-binary and RB trees are for binary trees. newbie wasn't sure how to adapt a RB tree to the non-binary case; this answer shows that you don't need to. That's why I don't see it as a catch-22 or circular answer. $\endgroup$ – D.W.♦ Nov 25 '15 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.