hash-db
hash-db copied to clipboard
samsquire
Use balancing binary trees
Any preference on type of self-balancing binary search tree? Red-black seems like an obvious choice, but was wondering what the other constraints are.
I'm not sure if it's a red black tree but you can calculate the height of every node and either left rotate or right rotate based on which side (left or right) is higher.
https://algorithmtutor.com/Data-Structures/Tree/Self-balancing-Binary-Search-Trees/
Are you looking to make a custom tree implementation or to use an external Python package? I did a quick search and found this package is well maintained: https://grantjenks.com/docs/sortedcontainers/performance.html
That said, using someone else's implementation might not be as fun or as good of a learning experience as writing a custom one.
I would definitely be down to do either of these and turn it into a PR. Let me know what you think.
My custom tree implementation is in datastructures.py.
I would like to learn how to change it to be self balancing.
I saw an implementation that checked the height of each node and if one side was higher than the other it would do a left rotate or right rotate. I would want to study what a rotate means as it's kind of complicated.
https://github.com/samsquire/hash-db/blob/master/datastructures.py
You're welcome to give it a try!
Samuel Michael Squire
On Wed, 11 May 2022, at 1:43 AM, Farley Knight wrote:
Are you looking to make a custom tree implementation or to use an external Python package? I did a quick search and found this package is well maintained: https://grantjenks.com/docs/sortedcontainers/performance.html
That said, using someone else's implementation might not be as fun or as good of a learning experience as writing a custom one.
I would definitely be down to do either of these and turn it into a PR. Let me know what you think.
— Reply to this email directly, view it on GitHub https://github.com/samsquire/hash-db/issues/3#issuecomment-1123053683, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAPEJVJHUF4LW4YHI3FKEQLVJL7ENANCNFSM443B7BCQ. You are receiving this because you authored the thread.Message ID: @.***>
I've got a PR for this up now. It is definitely a work-in-progress, so feel free to ask a bunch of questions or make suggestions: https://github.com/samsquire/hash-db/pull/7