4 ms·
What's the preferred way of implementing a binary tree, and how much more efficient is it over just nodes and references?
by woojoo666 4y ago
What's the preferred way of implementing a binary tree, and how much more efficient is it over just nodes and references?
- spinlock 4y agoThe heap implementation in Coran Leaderson and Revests’ Algorithms book is super interesting. But, I used to refer to that book as the cure for insomnia as an undergrad. It won’t be very engaging content to most people.
- vardhanw 4y agoIts Cormen, Leiserson, Rivest. Was it a spell check error or a deliberate misspell for some reason?
- spinlock 4y agoLol. That was all Seri. Now, I’m questioning her politics.
- marginalia_nu 4y agoI sadly think some of these subjects become sort of a snooze fest because at the time you are learning them, you are so far away from applying the patterns. It's far closer to stamp collection than any actual implementation for the average undergrad. Back first year when we had linear algebra, I was pretty much the only guy who absolutely aced the exam. Not because I was the smartest or hardest working, but because I applied everything we learned to a game I was building, a 3d spaceship simulator. Vector products, planar projections, rotation matrices, I mainlined all of it, I pored over the book in my spare time with great enthusiasm. For the rest of the class it was just yet concept after abstract concept being piled on with no place to apply them.
- marginalia_nu 4y agoAs alluded to in the sibling comment, implicit trees are a good starting point for trees that are to be reasonably dense. Removing explicit pointers reduces the size and increases the data locality. Depending on what manner of tree you've built, you can also iterate over these values in a fast and cache-friendly way.
- chudmeister 4y ago