7 ms·
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.
by shagie 2y ago
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 planning over the weekend (this was in the "we're redoing the class, teach it as it needs to be taught" type mandate) and he had us skip that section of the text. The fist lecture he was going off of overhead transparencies that he was writing as he lectured. The second lecture he gave us photocopies of hand written notes and diagrams.
Instead of AVL and red black trees, we instead learned about 2-3 trees and B trees.
For what it's worth, I still know how to do 2-3 trees from scratch.
Later I looked at AVL trees... and they still give me a headache.
- abhgh 2y agoRed-black trees use to make me anxious. I think the first time I grasped them was after watching Erik Demaine's lecture on the topic. For anyone interested it is this [1]; its still a very good reference on the topic! [1] https://videolectures.net/mit6046jf05_demaine_lec10/ https://videolectures.net/mit6046jf05_demaine_lec10/
- cassepipe 2y agoRB trees still make me anxious which is why I use AA trees instead https://en.wikipedia.org/wiki/AA_tree https://en.wikipedia.org/wiki/AA_tree
- deleted 2y ago[deleted]
- teruakohatu 2y agoI feel there must be better ways of learning the principles of algorithms than balancing trees. I suffered through RB trees.
- 082349872349872 2y agoThere are two fundamental things to teach in an algorithms course: 1) that there are many programs that implement the same algorithm, and many algorithms that implement the same function. 2) that there are a few basic tradeoffs we can make when implementing a function/customising an algorithm: space vs time, read vs write, deterministic vs indeterministic, etc. I'd guess trees have traditionally been used, because there's a whole zoo of them, which clearly presents (1) and allows (2) to be learned (in "cookbook" style) even if they're never explicitly presented (in "textbook" style).
- ajuc 2y agoSuffering is the point. It's like exercises in math or push-ups - if you find a way to do them effortlessly you won't develop the skills you are training for. I agree they suck tho.
- slaymaker1907 2y agoB-trees are definitely more useful, but I don’t think they’re really a good idea to start out with as your first balanced tree.
- 29athrowaway 2y agoLeft leaning red black trees are simpler to implement than the regular red black tree.
- skribanto 2y agoLeft leaning red black trees enforce extra constraints, which remove symmetries. This actually adds an edge case when instead you can just treat left/right rotations and comparisons as symmetric operations. Left Leaning Red Black Trees Considerer Harmful: https://www.read.seas.harvard.edu/~kohler/notes/llrb.html https://www.read.seas.harvard.edu/~kohler/notes/llrb.html
- saghm 2y ago> 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 reason, I've run into cases far more often where I need to maintain insertion order than sort order, but I'm not confident about whether this is due more to the type of stuff I work on or if it's just a more common requirement in general.
- globular-toast 2y agoThey'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"?
- masklinn 2y agoIf your concern is just arbitrary lookups then your baseline is a hashmap though.
- globular-toast 2y agoNot really. Hashmaps don't have guaranteed performance characteristics and require the "correct" hash function to work properly. In particular, their performance degrades as they become more "full" requiring a re-allocation to a table of generally n-times the size. Balanced trees could be regarded a more generic solution to the mapping problem and are more suitable in many applications.
- fanf2 2y agoTrees require a lot more memory indirections than hashmaps, which makes them slower to traverse. They require a lot more interior pointers, which makes them bigger. It’s easy for a hashmap to beat a tree.
- tgv 2y agoAVL isn't complicated. Insert the node as you would in a binary tree. Do that recursively. Then, when you return from inserting, you check at each level if the height of the tree under the left and right children differ at most 1. If not, you perform a little shuffle of the nodes, update the levels, and return to the previous level. That's all. The proof that that works is a bit complicated, though.
- e12e 2y agoI have a soft spot for red-black trees ever since reading about them in Dr. Dobbs - it's the first time I remember reading about a data structure (and it went mostly over my head at the time - but the fond memory remain): I believe it was the 1992 article by Bruce Schneier: https://jacobfilipp.com/DrDobbs/articles/DDJ/1992/9204/9204c/9204c.htm https://jacobfilipp.com/DrDobbs/articles/DDJ/1992/9204/9204c...
- DanielHB 2y ago> Later I looked at AVL trees... and they still give me a headache. Why? From what I remember AVL trees were much easier to implement than B-trees. Especially if using recursion.
- whizzter 2y agoInsertion in AVL tree's is fairly simple and doesn't really have any cascades so they are quite predictable, deletions on the other hand cascades upwards with a bunch of different imbalances and thus rotations(and post rotation balances) to be accounted for. Recently implemented them for an advanced hobby project and having a solid fuzzing tester in place really alleviated a lot of headaches in the long term since it was able to produce quite an exhaustive set of conditions.
- nayuki 2y agoB-tree deletions are quite complicated too, requiring stealing keys from either-side sibling or merging with either-side sibling. In practice, I find that a B-tree implementation is 2 to 3× the length of an AVL tree impl. I also fuzz-tested my implementations thoroughly. https://www.nayuki.io/page/avl-tree-list https://www.nayuki.io/page/avl-tree-list , https://www.nayuki.io/page/btree-set https://www.nayuki.io/page/btree-set , etc.
- DanielHB 2y agoYeah, this is what I was thinking too. The rebalancing on AVL is a bit tricky but once you grok it, it is not that much code...
- nayuki 2y agoI would not scoff at AVL trees. They are easy to prove correctness for, and admit a short implementation at ~100 lines. They're as short as AA trees, but AA trees are harder to prove with more cases. https://www.nayuki.io/res/aa-tree-set/BasicAvlTreeSet.java https://www.nayuki.io/res/aa-tree-set/BasicAvlTreeSet.java , https://www.nayuki.io/page/aa-tree-set https://www.nayuki.io/page/aa-tree-set B-trees require a much longer implementation than AVL trees. https://www.nayuki.io/page/btree-set https://www.nayuki.io/page/btree-set
- ncruces 2y agoAnother (immutable/persistent) AA tree implementation, in Go: https://github.com/ncruces/aa https://github.com/ncruces/aa
- harrison_clarke 2y agored black trees can be thought of as 2-4 trees, and they're way less headache-inducing when you do if you inline the red nodes into the black nodes, you get a 2-4 tree node. except that the 3-nodes have chirality. but then, you can just use a 2-4 tree AVL trees seem not worth learning. they have slightly different performance characteristics than red-black trees. but, if i care about performance beyond big O, i'm probably using a hash table or a cache-aware tree of some kind instead of a CS101 data structure