This week we covered AVL trees, 2-3 trees, heap trees, and hashing. Hashing is a slight departure from the structures we've covered more recently since it's superficially represented as something other than a tree. That said, it's still a type of mapping construct/process. The rotation operations used in the addition, removal, and ordering/balancing operations of the trees was new. For AVL trees, the professor provided a YouTube video that was an excellent supplement to our recorded lecture. It helped clarify things for me.
https://www.youtube.com/watch?v=msU79oNPRJc
As an interesting footnote, I also liked the example approaches to confirming that a number is a prime number. I don't have a deep knowledge of cryptology and number theory but I have heard that prime numbers play a big role.
https://www.geeksforgeeks.org/cpp/c-program-to-check-prime-number/
As usual, I was curious about real world applications of the concepts introduced this week. I found that the red-black tree at the core of the Linux completely fair scheduler (CFS) is a type of 2-3 tree. I pointed this out in the class discord channel. It's been part of the Linux kernel since v2.6.
https://developer.ibm.com/tutorials/l-completely-fair-scheduler/
No comments:
Post a Comment