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.
(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.