search

samsquire / hash-db

Experimental distributed pseudomultimodel keyvalue database (it uses python dictionaries) imitating dynamodb querying with join only SQL support, distributed joins and simple Cypher graph support and document storage
51 stars 1 forks source link

Use balancing binary trees #3

Open samsquire opened 3 years ago

farleyknight commented 2 years ago

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.

samsquire commented 2 years ago

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/

farleyknight commented 2 years ago

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.

samsquire commented 2 years ago

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: @.***>

farleyknight commented 2 years ago

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