11–20 of 78 posts
That is true on-disk, where you would not use BSTs anyway. In-memory, mid to high single digit values are practical. For instance iirc Rust’s btree (map and set) uses something like k=6.
Long ago, I was taking the sophomore level data structures and algorithms class. It was being transitioned from C to C++ and being taught by Professor DeWitt. I have vague memories of linked lists and then binary trees. ... And then we got to the spot where the syllabus from previous years had AVL trees and red black trees... and he scoffed at teaching it. And that I do remember. I suspect he had been doing lecture p…
> Instead of AVL and red black trees, we instead learned about 2-3 trees and B trees When we first were taught about B trees in my databases course in college, he professor quipped something like "these are the reason you'll never actually use a red-black tree in practice". I've actually found that in practice I rarely ever up actually needing to use any sort of data structure that maintains sort order; for whatever…
Long ago, I was taking the sophomore level data structures and algorithms class. It was being transitioned from C to C++ and being taught by Professor DeWitt. I have vague memories of linked lists and then binary trees. ... And then we got to the spot where the syllabus from previous years had AVL trees and red black trees... and he scoffed at teaching it. And that I do remember. I suspect he had been doing lecture p…
> Instead of AVL and red black trees, we instead learned about 2-3 trees and B trees When we first were taught about B trees in my databases course in college, he professor quipped something like "these are the reason you'll never actually use a red-black tree in practice". I've actually found that in practice I rarely ever up actually needing to use any sort of data structure that maintains sort order; for whatever…
I've had the exact opposite experience, so I'm guessing it has a lot to do with the type of stuff you've (and I've) worked on.
Long ago, I was taking the sophomore level data structures and algorithms class. It was being transitioned from C to C++ and being taught by Professor DeWitt. I have vague memories of linked lists and then binary trees. ... And then we got to the spot where the syllabus from previous years had AVL trees and red black trees... and he scoffed at teaching it. And that I do remember. I suspect he had been doing lecture p…
> Instead of AVL and red black trees, we instead learned about 2-3 trees and B trees When we first were taught about B trees in my databases course in college, he professor quipped something like "these are the reason you'll never actually use a red-black tree in practice". I've actually found that in practice I rarely ever up actually needing to use any sort of data structure that maintains sort order; for whatever…
I think I've had to implement my own traversable data structure literally only in interviews
For instance, fewer values per node means less information to copy when copying the node. Locking is more granular with fewer values per node because fewer values are locked at a time.
The binary structure also makes it possible to support randomized balancing and self-adjusting strategies like splay trees.
I am disappointed to still see frequent mention of red-black trees – I see no reason for red-black trees to ever be the best choice in practice, or in theory, or in school. LBST's (logarithmic binary search trees) [1] are generally simpler, more intuitive, and more efficient [2] than red-black trees. They also support positional access inherently, so the balancing information is useful (subtree size).
[1] https://www.semanticscholar.org/paper/A-New-Method-for-Balan... [2] https://rtheunissen.github.io/bst
Earlier quoted context omitted.
> Instead of AVL and red black trees, we instead learned about 2-3 trees and B trees When we first were taught about B trees in my databases course in college, he professor quipped something like "these are the reason you'll never actually use a red-black tree in practice". I've actually found that in practice I rarely ever up actually needing to use any sort of data structure that maintains sort order; for whatever…
They're not about maintaining sort order, though? They're about arbitrary lookup. Or do you mean "if I had to pick one nice side effect"?
Long ago, I was taking the sophomore level data structures and algorithms class. It was being transitioned from C to C++ and being taught by Professor DeWitt. I have vague memories of linked lists and then binary trees. ... And then we got to the spot where the syllabus from previous years had AVL trees and red black trees... and he scoffed at teaching it. And that I do remember. I suspect he had been doing lecture p…
> Instead of AVL and red black trees, we instead learned about 2-3 trees and B trees When we first were taught about B trees in my databases course in college, he professor quipped something like "these are the reason you'll never actually use a red-black tree in practice". I've actually found that in practice I rarely ever up actually needing to use any sort of data structure that maintains sort order; for whatever…
> Practical B-trees often use fairly large values of k (e.g., 100) and therefore offer tight bounds -- in addition to being more cache-friendly than binary search trees. That is true on-disk, where you would not use BSTs anyway. In-memory, mid to high single digit values are practical. For instance iirc Rust’s btree (map and set) uses something like k=6.
... for absl::btree_set, nodes currently have 62 children ...
Earlier quoted context omitted.
They're not about maintaining sort order, though? They're about arbitrary lookup. Or do you mean "if I had to pick one nice side effect"?
If your concern is just arbitrary lookups then your baseline is a hashmap though.
Long ago, I was taking the sophomore level data structures and algorithms class. It was being transitioned from C to C++ and being taught by Professor DeWitt. I have vague memories of linked lists and then binary trees. ... And then we got to the spot where the syllabus from previous years had AVL trees and red black trees... and he scoffed at teaching it. And that I do remember. I suspect he had been doing lecture p…