Geek Answers Handbook

Balanced binary search Tree data is stored only in leaves

I bought a little book on computational geometry, and reading it here and there, I often stumbled upon using this special kind of binary search tree. These trees are balanced and should only store data in vacation nodes, internal nodes should only store values ​​to search through the leaves.

illustration of a binary search tree

The image shows a tree of examples where the leaves are rectangles and the inner nodes are circles.

I have two questions:

  • What is the advantage of storing data in internal nodes?
  • For training, I would like to implement such a tree, so I thought it might be a good idea to use the AVL tree as the basis, but is that so?

And last, but not least, it is important to emphasize the fact that I am dealing with this material because I want to know something, therefore every useful resource is very welcome. Thanks, come on, hello ...

+6
source share
5 answers
  • There are some tree-like data structures that by design require that no data be stored in internal nodes, such as Huffman code trees and B + trees . In the case of Huffman trees, the requirement is that none of the two sheets have the same prefix (i.e., the path to node 'A' is 101, while the path to node 'B' is 10). In the case of B + trees, this is due to the fact that it is optimized for block search (this also means that each internal node has many children and that the tree is usually only a few levels).
  • Sure! The AVL tree is not extremely complex, so it is a good candidate for training.

Hope this helps.

+2
source

ad 1 . In general, there is no advantage to not storing data in internal nodes. As an example, the RB tree is also a balanced tree and stores its data in internal nodes instead of leaves (see http://en.wikipedia.org/wiki/Red-black_tree )

ad 2 : IMHO this is most definitely. (a good idea)

+1
source

Usually for binary search trees other types of binary trees are used with data on leaves instead of internal nodes, but they are quite rare.

One of the reasons you probably WANT to do this is the educational process - often EASIER implements the binary search tree this way and then the traditional way. What for? Almost completely due to removal. Removing a leaf is usually very simple, while removing the interior of a node is more complicated / messy. If your data is only on the leaves, then you are always in the easy case!

It is worth considering where the keys to the internal nodes came from. Often these are duplicate keys that are also on the leaves (with data). Later, if the key on the sheet is deleted, the key in the internal nodes may still hang.

+1
source

One of the advantages of saving data only in leaf nodes (e.g. B + tree) is that scanning / reading data is extremely simple. Leaf nodes are connected to each other. So, to read the next element, when you are at the “end” (right or left) of the data within a given leaf node, you simply read the link / pointer to the next (or previous) node and go to the next page of the leaf.

With tree B, where the data is in each node, you need to go through the tree to read the data in order. This is certainly a well-defined process, but perhaps more complex and usually requires more status information.

0
source

I read the same book, and they say that this can be done anyway, by storing data on external or internal nodes.

The trees they use are red and black.

In any case, here is an article in which data is stored on the internal nodes of the red ebony tree, and then these data nodes are combined in a list.

Balanced binary search tree with doubly linked list in C ++ by Arjan van den Boogaard

http://archive.gamedev.net/archive/reference/programming/features/TStorage/default.html

0
source

More articles:


All Articles