Click here to Skip to main content
14,486,577 members

Welcome to the Lounge

   

For discussing anything related to a software developer's life but is not for programming questions. Got a programming question?

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.
 
GeneralRe: my apologies to the CodeProject community for a recent inappropriate Lounge post Pin
BillWoodruff3-Jan-20 1:30
mveBillWoodruff3-Jan-20 1:30 
GeneralRe: my apologies to the CodeProject community for a recent inappropriate Lounge post Pin
Eddy Vluggen3-Jan-20 1:49
professionalEddy Vluggen3-Jan-20 1:49 
JokeRe: my apologies to the CodeProject community for a recent inappropriate Lounge post Pin
Daniel Pfeffer2-Jan-20 23:56
professionalDaniel Pfeffer2-Jan-20 23:56 
GeneralRe: my apologies to the CodeProject community for a recent inappropriate Lounge post Pin
BillWoodruff3-Jan-20 1:32
mveBillWoodruff3-Jan-20 1:32 
Generalfigured out something cool, a specialization for integer binary trees Pin
honey the codewitch2-Jan-20 4:23
mvahoney the codewitch2-Jan-20 4:23 
GeneralRe: figured out something cool, a specialization for integer binary trees Pin
W Balboos, GHB2-Jan-20 4:33
mveW Balboos, GHB2-Jan-20 4:33 
GeneralRe: figured out something cool, a specialization for integer binary trees Pin
honey the codewitch2-Jan-20 4:36
mvahoney the codewitch2-Jan-20 4:36 
GeneralRe: figured out something cool, a specialization for integer binary trees Pin
Member 79891222-Jan-20 7:34
MemberMember 79891222-Jan-20 7:34 
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 Smile | :) ).

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 Smile | :)
GeneralRe: figured out something cool, a specialization for integer binary trees Pin
honey the codewitch2-Jan-20 7:41
mvahoney the codewitch2-Jan-20 7:41 
GeneralRe: figured out something cool, a specialization for integer binary trees Pin
Jörgen Andersson2-Jan-20 5:51
professionalJörgen Andersson2-Jan-20 5:51 
GeneralRe: figured out something cool, a specialization for integer binary trees Pin
honey the codewitch2-Jan-20 5:53
mvahoney the codewitch2-Jan-20 5:53 
GeneralRe: figured out something cool, a specialization for integer binary trees Pin
Shuqian Ying2-Jan-20 8:59
MemberShuqian Ying2-Jan-20 8:59 
GeneralRe: figured out something cool, a specialization for integer binary trees Pin
Daniel Pfeffer3-Jan-20 0:02
professionalDaniel Pfeffer3-Jan-20 0:02 
GeneralRe: figured out something cool, a specialization for integer binary trees Pin
Member 79891222-Jan-20 6:12
MemberMember 79891222-Jan-20 6:12 
GeneralRe: figured out something cool, a specialization for integer binary trees Pin
honey the codewitch2-Jan-20 6:13
mvahoney the codewitch2-Jan-20 6:13 
GeneralComing back to work after a long vacation feels weird. Pin
Maximilien2-Jan-20 2:59
MemberMaximilien2-Jan-20 2:59 
GeneralRe: Coming back to work after a long vacation feels weird. Pin
musefan2-Jan-20 3:02
Membermusefan2-Jan-20 3:02 
GeneralRe: Coming back to work after a long vacation feels weird. Pin
OriginalGriff2-Jan-20 3:13
mveOriginalGriff2-Jan-20 3:13 
GeneralRe: Coming back to work after a long vacation feels weird. Pin
musefan2-Jan-20 3:57
Membermusefan2-Jan-20 3:57 
GeneralRe: Coming back to work after a long vacation feels weird. Pin
honey the codewitch2-Jan-20 4:27
mvahoney the codewitch2-Jan-20 4:27 
GeneralRe: Coming back to work after a long vacation feels weird. Pin
OriginalGriff2-Jan-20 4:37
mveOriginalGriff2-Jan-20 4:37 
GeneralRe: Coming back to work after a long vacation feels weird. Pin
honey the codewitch2-Jan-20 4:38
mvahoney the codewitch2-Jan-20 4:38 
GeneralRe: Coming back to work after a long vacation feels weird. Pin
GuyThiebaut2-Jan-20 3:03
professionalGuyThiebaut2-Jan-20 3:03 
GeneralRe: Coming back to work after a long vacation feels weird. Pin
Maximilien2-Jan-20 4:20
MemberMaximilien2-Jan-20 4:20 
GeneralRe: Coming back to work after a long vacation feels weird. Pin
kmoorevs2-Jan-20 3:24
Memberkmoorevs2-Jan-20 3:24 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.