2
$\begingroup$
  1. Why do some search trees store all elements in the leaves, while other search trees don't? One difference that makes is whether a successful search may end up in an internal node.

    For m-ary search trees, the former case will need more leaves and more heights than the latter. Is this the benefit of not storing all the elements in the leaves?

    Is storing all the elements in the leaves only for looking consistent? Does it have some benefits? Someone said that

    Contrary to what you said, in the three examples you gave, the internal nodes also contain values.

    In a B+ tree for example, all values are located in the leaves, the internal nodes only contains keys

    "This is interesting only when the data is separated in a key and some other value (as in a database). This allows more keys to go in the internal nodes, limiting the tree depth. When the nodes are on a slow medium, this limits the time needed to go to the data." But I don't quite understand that, because

    • when we choose to store records in the internal nodes, we don't need to store the actual records in the internal nodes, but can always store with each key a pointer to the actual records, so that we can save space to store more keys. So I don't understand why he said that "This allows more keys to go in the internal nodes".

    • as mentioned above, I guess storing elements in the leaves rather than also in internal nodes will make the search trees higher, so I don't understand why he said that storing all the elements in the leaves can "limit the tree depth".

  2. For B-trees and 2-3 trees, why do some references define them so that all the elements are stored in the leaves, while other references don't? Note that 2-3 trees are special B-trees, according to Aho's book.

    I just found that

    • the definitions of 2-3 trees and B trees in Aho's Data Structures and Algorithms store all the elements in the leaves, so that a successful search always end up in a leaf enter image description here enter image description here

    • But the examples of 2-3 trees and B trees in Wikipedia and also in wikipedia and in Sedgewick's Algorithms (also see the first picture below) and in CLRS (see the second picture below) store only some elements in the leaves, so that a successful search may end up in an internal node.

      enter image description here
      enter image description here

  3. For binary search trees, why all the references define them so that not all elements are stored in the leaves?

    I haven't seen any reference that define binary search trees with all elements defined in the leaves, or am I missing it?

    Can Huffman trees be viewed as binary search trees where all the elements are defined in the leaves?

  4. Is balancing the only or most important aspect where 2-3 trees improves over binary search trees?

    From the above questions, I mentioned that some references define 2-3 trees so that all the elements are stored in the leaves, while others don't, and within my readings, binary search trees are always defined so that not all the elements are stored in the leaves. Is whether search trees store all elements in the leaves an important aspect to distinguish between 2-3 trees and binary search trees, as important as the balancing aspect?

Thanks.

$\endgroup$
  • $\begingroup$ That's not true for the 2-3-trees I know. Which/whose definition are you using? $\endgroup$ – Raphael Oct 17 '16 at 8:50
  • 1
    $\begingroup$ Please don't keep versions of the question; the software already keeps revisions. Every version should be a self-sufficient, concise question. $\endgroup$ – Raphael Oct 17 '16 at 12:55
  • $\begingroup$ So you still ask several questions per post. Why? $\endgroup$ – Evil Oct 17 '16 at 17:42
1
$\begingroup$

You mention that "2-3 trees are special B-trees". Note that B-trees are different from B+-tree. In a B-tree, internal nodes also store part of the keys, while in a B+-tree, keys are all stored in the leaves. Therefore, 2-3 trees, as B-trees of order 3 by definition, can have elements in their internal nodes.

$\endgroup$

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.