The Lounge is rated Safe For Work. If you're about to post something inappropriate for a shared office environment, then don't post it. No ads, no abuse, and no programming questions. Trolling, (political, climate, religious or whatever) will result in your account being removed.
I really have a hard time understanding how you are thinking.
You may of course traverse a tree from left to right and from right to left, to read the values in one order or the opposite, but that doesn't make it doubly linked. There are neither forwards nor backwards links in the tree, only subtree links.
B-trees (which are usually fare more exciting and useful than binary trees - and far more space efficient!) must have forward links between blocks at the same level, at both index and leaf (data) levels, and I have seen several implementations with backwards links (although they are not strictly required). I guess the same holds for predecessors of B-trees, such as ISAM structures, but you have to dig up some really outdated textbooks to find much about them. Generally speaking, any B-tree variant is an improvement.
What is the advantage of a binary tree? It takes at least one pointer for each value. Leaf nodes "waste" the space for two pointers, and for an unbalanced tree, lots of the internal nodes loose space to a null pointer. Even for a full and perfectly balanced tree (all internal nodes have non-null sons) the space overhead is 1.5 pointer per value.
Balancing a binary treee is rather costly - in particular if three are multiple accessors: For all practical purposes, you must lock the entire tree while you are doing the balancing. That's exactly why B-trees were developed: In a multiuser environment, you can do the balancing locking only a single node at a time.
I see binary trees as useful as a student exercise. When you start handling Real Data in an production environment, you need B-trees.
For small, temporary data within a single thread, you could of course say that locking and balancing of the tree is of no consern. But then you rarely have a need for the tree structure at all. You might as well put the data into a linear array, wasting no space on pointers, and do a binary search for the value you are searching for. In my student days, our professor told us to stop that binary search when the remaining interval was down to 8 values, and switch to a simple sequential search from there - binary search administration is too costly for small intervals. We didn't trust him, but when we tried to set up real tests, we couldn't even show that a breakoff at 16 made sequential search more costly.
One reason to use trees is when you do a huge amount of inserting. With anything but B-trees, you could easily end up with an extremely unbalanced tree. If inserting come in batches, appending them to a separate array in unsorted order, and periodically sorting this new elemnts array with an NlogN method (where N is the number of new elements) before merging them with the full list, which is an O(M) operation where M is the size of the full list, is in most cases far more efficient.
Curiously, I have spent a lot of vacation time this Youle on an old hobby project - a basic driver for a pure FSM implementation of protocols. This requires an efficient implementation of a sparsly populated 3D state transition table. (The main two dimensions are the states and the events, but some table cells have a sequence of alternatives, guarded by predicates to be tested one by one.) I considered several alternatives, from plain 2D dirctly state/event indexed arrays to linked lists to dictionaries (i.e. hash tables). I ended up with dense arrays, with a two-step lookup of index limits for the "inner" array that is sequentially traversed. None of the alternatives come anywhere close to what I ended up with, neither in time performance nor in memory efficiency. It should be noted that the tables are generated, not hand written, but in a rather primitive way; we are not talking about generating LALR tables! (Which, I must admit, I never got a complete understanding of, even though I have been lecturing about them ).
Hardware has changed a lot over the years, with ever more prefetch and lookahead (whatever the difference is...), caches etc. Often, it causes locality to be essential to performance. Sequential array search is more or less synonymous with locality. Accessing one more element, in index order, is like adding one instruction to a tight loop: It is hardly noticeable on the execution time. Accessing a tree with pointers everywhere both defeats CPU caching (to some degree) and it could trigger a significant amount of hard page faults in environments where physical memory space is scarce. So my vote goes for higher respect for sequential searches through packed arrays
(It's not just binary trees. but i get into that at the link)
The reason the binary tree is useful to me specifically is I'm trying to speed up an already fast port of lex (flexish tho) to C# - it's called gplex. Unfortunately, it stores things as a binary tree. I don't understand how it's using it well enough to change the underlying data structure, but i can fix this:
internal TreeNode(int mn, int mx, int vl)
min = mn; max = mx; value = vl;
I didn't write this class. I just don't like lKid or rKid being TreeNode classes. That's crap use of the heap and even though heap is cheap in .net it isn't free. This is for an nfa/dfa lexer. i think it uses both. it can backtrack, but it can also do it without that overhead.
Also in terms of binary trees, you can achieve excellent locality using a splay tree but i find that in almost all cases, the moving the tree around is more costly than what you save by locality.
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
for static or constant trees, this is more efficient, but if the trees change (additions, deletions, change parents, etc) during their life time, the OP's method has an additional level of indirection so that it's more flexible and easier to manage ...
Long time ago, in my student days, I was engaged as a TA for the freshman "101 Programming" course, with a little above 1000 students. This was in the transition from Fortran to Pascal as the primary programming language. Ssome of the faculties at the Tech U was very conservative: Real Engineers program in Fortran! Pascal is for sisses!
So the course came in two varieties: Students of Chemistry and Construction Engineering learned Fortran, most others learned Pascal programming. The topics were the same, and three out of four homework assignments were identical. For the last one, the Pascal students were to create a linked list and define some operations on it. The Fortran student did something else, I don't remember what.
I was approached by this chemistry girl, good-looking and friendly, but she was a little crossed: She had heard that those Pascal students were learning something that she didn't learn in the Fortran course. Why not? Why couldn't they all learn it? Well... Fortran doensn't have pointers, so it isn't possible. But what are pointers? I gave her a very simple explanation - it is not a value, but it tells you where to find the value. Like this list, you have the three data fields in each record, and a fourth one that tells where the next record is.
I may have said something like "think of memory as large array, and that fourth value is the array index of the next record". I must have, because a week later, this young lady was back, telling that she had obtained a copy of the Pascal homework assignment. Now she had programmed it in Fortran, using array indexes as pointers. It appearently worked, but if I would take a look at it, she would be happy...
That lady certaily neither looked like nor behaved as the stereotype of a top rate engineer, but I have a gut feeling that she had the qualities required (not for "stereotype" but for "top rate" )! I never saw her after that 101 Programming course, so I can't tell for sure, but I am quite sure she has had a successful career.
I guess it is quite obvious why I came to think of this old memory when reading your post.