search

msambol / dsa

Data structures and algorithms in X minutes. Code examples from my YouTube channel.
https://youtube.com/michaelsambol
MIT License
459 stars 100 forks source link

Children bug #6

Closed Zogebang closed 1 year ago

Zogebang commented 1 year ago

https://github.com/msambol/dsa/blob/5579be5aff4fc005bfe6c108d2e4c2afc6ad7945/trees/b_tree.py#L46C3-L46C3 So the issue is in the lines 45-46. If y is not a leaf, we reassign y's children to y & z. We can max have 2*t children, in this case 6. Using lines 45-46, we reassign only 1,2,4,5,6 children, missing the third child due to a logic error. To prevent it, we must simply do (y.children = y.children[0: t]), unstead of (y.children = y.children[0: t - 1]), so the third child is not missing. To test that, I used Your delete example, but after all the deletions, inserted 26. With the old wersion of the code, before inserting 26, we had 18 values in our tree, after inserting 26 we have only 17 values, as 2 of them are missing, which are values 32 and 39. Using the fixed version of line 46, the code seems to be working properly, having 19 values after inserting and not missing any node.

msambol commented 1 year ago

Thanks for finding this! Do you mind submitting a pull request? :)

Zogebang commented 1 year ago

I would like to, but I didn't get how to do so)

msambol commented 1 year ago

Can I teach you? It will be good to learn this. Start here: https://www.tomasbeuzen.com/post/git-fork-branch-pull. Let me know if you get stuck.

msambol commented 1 year ago

Hey @Zogebang. I made this change in https://github.com/msambol/dsa/commit/5851492d7aa1d98d67a030384ba48a3e3578ff45. Thanks for the feedback!