add GetMin/DeleteMin, GetMax/DeleteMax function to redblacktree

huydx commented

2016-03-13 10:23:44 +00:00

(Migrated from github.com)

hi @emirpasic As redblacktree maintain order of elements, it should be natural to add interface to poll the min and max value from the tree. I've implemented the logic to do so, and I also fixed the wrong test message at here

Please take a look if you have time.

Thank you.

hi @emirpasic As redblacktree maintain order of elements, it should be natural to add interface to poll the min and max value from the tree. I've implemented the logic to do so, and I also fixed the wrong test message at [here](https://github.com/emirpasic/gods/blob/master/trees/redblacktree/redblacktree_test.go#L102) Please take a look if you have time. Thank you.

huydx commented

2016-03-18 00:12:36 +00:00

(Migrated from github.com)

ping @emirpasic

emirpasic commented

2016-03-18 00:22:57 +00:00

(Migrated from github.com)

@huydx I've got you brother, thanks for the input. You're right that this feature is very natural for redblack tree. However, I will need to evaluate this idea from a higher architectural point of view, i.e. is this only the case with the redblack tree or should certain datastructures have this defined in their interface or perhaps the container interface even, despite the fact that its computation would be O(n) in some cases. I have not seen that in STL, Ruby, Javascript or Java, they rather provide methods or hooks where you inject this evaluation usually through some type of iterator pattern or evaluation function. So excuse if I'll take longer with this, but it's important that it's implemented the right way across the project, not just for one case.

emirpasic commented

2016-03-23 05:40:28 +00:00

(Migrated from github.com)

@huydx

Please check #3

It includes the requested feature (with minor bug fix), documentation and example. If you are happy with that approach, please let me know and I will merge #3 and close this PR.

In short, I did not integrate your changes directly into the red-black tree implementation for two reasons:

Adding features ad hoc leads to messy libraries.
I have not found any examples in any other libs where this was done. The logic is just too problem specific and thus out of scope of this and similar projects.

However I have exposed the nodes in the red-black tree, so that you can implement your logic by embedding. Please check out the following example of how to extend the red-black tree with your case.

I hope that we both can be happy with this solution, daijoubu desu ka?

@huydx Please check #3 It includes the requested feature (with minor bug fix), documentation and [example](https://github.com/emirpasic/gods/blob/master/examples/redblacktreeextended.go). If you are happy with that approach, please let me know and I will merge #3 and close this PR. In short, I did not integrate your changes directly into the red-black tree implementation for two reasons: - Adding features ad hoc leads to messy libraries. - I have not found any examples in any other libs where this was done. The logic is just too problem specific and thus out of scope of this and similar projects. However I have exposed the nodes in the red-black tree, so that you can implement your logic by embedding. Please check out the following [example](https://github.com/emirpasic/gods/blob/redblacktree-node-export/examples/redblacktreeextended.go) of how to extend the red-black tree with your case. I hope that we both can be happy with this solution, daijoubu desu ka?

mort666 referenced this pull request from a commit

2026-09-07 14:30:33 +00:00

Merge pull request #2 from Arvin619/docs/generic-update

Pull request closed

Please reopen this pull request to perform a merge.

Rows
Columns

add GetMin/DeleteMin, GetMax/DeleteMax function to redblacktree #2

Pull request closed