5
$\begingroup$

Given N items you want to put into a tree, think very generally here like a phone tree, and your goal is to keep the tree from getting "too wide" and "too deep". How many children (K) do you put at each node?

I seem to recall hearing of some proof, many years ago, K was best when set to Euler's number. Therefore in real applications if you must choose a single number you pick 3 children and the tree should end up closely balanced between depth and width. In other words, binary trees tend to be too deep, and 5-trees are "too wide".

Some searching of the 'net and reading some tree designs on Wikipedia has not proved fruitful but perhaps I am dreaming up a false memory?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Can you be more precise in what you mean by "too wide" and "too deep"? What exactly are you trying to optimize, and why? $\endgroup$
    – Yuval Filmus
    Feb 11, 2015 at 1:40
  • $\begingroup$ Search trees, or just any trees? Do you know B-trees? $\endgroup$
    – Raphael ♦
    Feb 11, 2015 at 11:40
  • $\begingroup$ Yuval: I talking about average node children as compared to total tree depth. My memory was one where depth was minimized without having large numbers of children per node. Does this mean avg children equal to depth? maybe? $\endgroup$
    – RudeDude
    Feb 12, 2015 at 14:57
  • $\begingroup$ Raphael: I don't think I want to limit this to just search trees. The concept I recall focused on a phone menu system since you don't want to listen to 9 options on each level of the tree nor do you want to drill down through too many layers of the tree to reach your desired option. $\endgroup$
    – RudeDude
    Feb 12, 2015 at 15:39
  • $\begingroup$ This is a reasonably related SE question cs.stackexchange.com/questions/47453/… $\endgroup$
    – RudeDude
    Apr 21, 2016 at 13:32

3 Answers 3

Reset to default
3
$\begingroup$

This sounds as follows.

  • The answer is that the optimal number of children in a tree is $e$. What was "optimal" in the question?

One such question is as follows.

  • Let us construct a tree of $N$ nodes. Imagine we arrange them into a perfect $K$-ary tree with $L$ levels of internal vertices. When we search over such tree, assume that the worst case is that we visit $K$ vertices in each of the $L$ internal levels, making the search $O (K \cdot L)$. What is the optimal $K$ as $N$ tends to infinity?

Here, we select $K$, and then $L$ is computed as $log_K N$.

When we think about it a bit, here is an arithmetic rephrase.

  • We have a number $N$. We want to express some integer $M \ge N$ as a product of integers $S_1 \cdot S_2 \cdots S_L$ so that the sum $S_1 + S_2 + \ldots + S_L$ is minimal possible. When $N$ tends to infinity, what will be the sequence $\{S\}$?

The values $S_1, S_2, \ldots, S_L$ are the number of children at levels $1, 2, \ldots, L$, respectively. If we had a perfect $K$-ary tree, all our $S_i$ would be equal to $K$, but we lifted the restriction that they are all equal: the essence of the solution remains the same.

When we don't insist that $N$ and $S_i$ are integers, after performing some basic calculus, we can see that the optimal answer is to pick all $S_i$ close to $e$. Note that the closest integer to $e$ is $3$. So for the integer version, the optimal answers turn out to be of the following forms: $$(3 \cdot 3 \cdots 3)$$ $$(3 \cdot 3 \cdots 3) \cdot 2$$ $$(3 \cdot 3 \cdots 3) \cdot 2 \cdot 2$$

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Yes, thank you for this response. This is definitely the framing that it needed so that both my question and the answer are covered. $\endgroup$
    – RudeDude
    Jun 29, 2018 at 13:40
0
$\begingroup$

I found this paper that talks about size-balance k-ary trees. Maybe you'll find it helpful.

Paper citation:

CHA, S. (2012). On Complete and Size Balanced k-ary Tree Integer Sequences. INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS AND INFORMATICS, 6(2), 8-8. Retrieved April 14, 2015, from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.352.3650&rep=rep1&type=pdf

Improve this answer
$\endgroup$
3
  • $\begingroup$ Interesting paper. Kind of dense but might touch on what I'm talking about after further reading. The author focuses on integer sequences of these balanced trees but doesn't talk about the relation between node degree and depth. $\endgroup$
    – RudeDude
    Feb 12, 2015 at 15:36
  • $\begingroup$ Can you summarize the key points from the paper? Can you edit the question to include a full citation to the paper, including title, authors, and where published, so we can find it again if the link dies? We tend not to like link-only answers, as they become useless if the link disappears -- and because we want to contribute new, useful content, not just be a link farm. $\endgroup$
    – D.W. ♦
    Apr 14, 2015 at 0:11
  • $\begingroup$ Hope it works for you! @D.W. $\endgroup$
    – David Merinos
    Apr 14, 2015 at 1:01
0
$\begingroup$

If we want to have same depth as width in the menu system, we will want to have a tree with $K$ nodes in each menu, and have have $K$ depth. If all the data resides on leaves then we need to solve $K^K \geq n > (K-1)^{K-1}$. We can solve this using Lambert function. Solving $x^x = y$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Is there a motivation why we'd want to have the same depth as width? Is the goal to minimize the total number of items that the user sees during a single interaction, or something? I'd expect that the total number of items the user has to see is $DW$, where $D$ is the depth and $W$ is the width. It's not clear why $D=W$ would be an optimal choice there -- is there a reason why that would be optimal? For instance, it seems like width $2$ and depth $K \lg K$ will be better than width $K$ and depth $K$ (product $2 K \lg K$ is smaller than product $K^2$). $\endgroup$
    – D.W. ♦
    Apr 9, 2016 at 0:36
  • $\begingroup$ @D.W. I went with my feeling. There is a whole lot of research done by the HCI people. There is a depth width tradeoff in designing menus. The issue is human understanding of the complexity of the menu and not the size, if I understand correctly. Please refer lap.umd.edu/poms/chapter8/chapter8.html and related matter. And I thought this is what OP wanted, again this is my guess. $\endgroup$
    – Sarvottamananda
    Apr 9, 2016 at 14:57
  • $\begingroup$ @Shreesh yeah I'm not being super great at generating a design spec here because I was mostly trying to recall a ghost of a memory. $\endgroup$
    – RudeDude
    Apr 21, 2016 at 12:44
  • $\begingroup$ Sorry, premature enter key (some sites don't need the shift+enter). We want users (tree searches) to find the result as quickly as possible. When listening to a phone tree the list of items can take a long time to read (K children) but it can also take a long time to dig deep in the tree (the $N^{(1/K)}$ approximate depth). My weak recollection that this was presented as a phone tree optimization so the large number of children-per-node may have been the primary influence on search performance. $\endgroup$
    – RudeDude
    Apr 21, 2016 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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