OK, I’ve come up across a representation for a rooted tree data structure where each node can have an arbitrary number of children. I’d like to know what it is called (if, indeed, it has a name) so that I can do a bit more research about it and find out some good algorithms for manipulating it.
Each node consists of a ‘left’ number and a ‘right’ number. It also has a ‘depth’ number, but I believe this is just for efficiency and not an integral part of the structure. The left and right numbers form a range. For leaf nodes, this range is usually, but doesn’t have to be, 1 (i.e. left and right are consecutive), but for parent nodes, the range is large enough to contain the ranges of all of its children. Parent-child relationships are represented by having the child’s range falling entirely within the parent’s.
For example, this tree:
R___
/|\ \
/ | \ \
A B C D
/| \
/ | \
m n o
|\
| \
1 2
could be defined as these nodes:
node l r d
---- -- -- --
R 0 19 0
A 1 2 1
B 3 12 1
C 13 16 1
D 17 18 1
m 4 5 2
n 6 11 2
o 14 15 2
1 7 8 3
2 9 10 3
I included the depths just in case I’m mistaken and they are necessary.
This data structure is being used to store a tree of web pages in a database. This appears to be more efficient for traversing the tree than the traditional scheme of storing a parent id with each node, but moving nodes around the tree appears to be very troublesome, especially if the node being moved already has many descendants.
Hmm, doesn’t look like a B-tree. Unless I’m misreading the information about them, each node in a B-tree has lower and upper bounds on the number of child nodes. In this tree, every node can have any number of children. Also, from what I can tell, the purpose of a B-tree is to store ordered data efficiently. This tree’s sole purpose is to preserve the tree-like relationship between nodes.
I’ll bump this thread to see if anyone has any other thoughts.
I’m probably wrong in this, but if one were to add nodes going out in all directions instead of just down (which I’m pretty certain you did just to conserve space), it reminds me of a snowflake schema, used in data warehousing.
It’s been a while since I went to Ralph Kimball’s seminar on this, so as I said, I’m probably wrong.
Do you have any idea what it would be used for? From my reading on B-trees, they would be used for maintaining a balanced tree. B-trees have all leaves at the same depth. This one doesn’t, and doesn’t appear to be good for balancing.
Maybe it is useful for storing data where you know the probable distribution beforehand?
Even if it’s not strictly a B tree, you might be able to find information by searching on B tree variants. Alternatively, you could go here and search for every kind of tree they have.
It’s not a B-tree. A B-tree is a balanced tree in which each of the internal nodes has between m/2 and m children, where m is the order of the tree (the root node may have fewer children). Each leaf node in a B-tree is the same distance from the root. In the example the leaf nodes are different distances from the root, and the number of children for internal nodes varies from 1 to 4 (a ratio of greater than 2 to 1).
I would suggest looking at Sorting and Searching (volume 3 of The Art of Computer Programming by Donald Knuth ). This book defines many different search tree structures and gives the algorithms for maintaining them.