Timeline for Can you define node pointers in a base binary tree class?
Current License: CC BY-SA 4.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 16, 2021 at 10:39 | history | edited | Doc Brown | CC BY-SA 4.0 | Typos fixed |
| Sep 16, 2021 at 8:53 | vote | accept | yomag1234 | ||
| Sep 16, 2021 at 8:54 | |||||
| Mar 16, 2021 at 9:21 | comment | added | yomag1234 | @DocBrown As I've said previously, I need to save the attributes so I can provide step-by-step sorting, so in every step partition() is called only once, on the appropriate node. If that node is sorted, we move onto its children and so on. If the variables are local to the functions, they go out of scope and I can't continue sorting where I left off in the previous step. | |
| Mar 16, 2021 at 7:17 | comment | added | Doc Brown | @yomag1234: you still did not tell us about your use case, this whole post reads like an XY problem, where you ask me if solution Y makes sense when I don't know X. Let me ask differently: why do you need to keep track of the forementioned attributes after the algorthm was run? What are you planning to do with these attributes afterwards? Why do they have to stay in that binary tree? What is your intent behind this? | |
| Mar 16, 2021 at 7:13 | comment | added | yomag1234 | @DocBrown I do it so I can call partiton() and other functions for each node in the binary tree. Is there a more sensible way to do this? | |
| Mar 15, 2021 at 22:26 | comment | added | Doc Brown | @yomag1234: technically not, but I have a hard time to imagine a use case where this would make sense. | |
| Mar 15, 2021 at 21:59 | comment | added | yomag1234 | @DocBrown yeah I do, is that problematic somehow? | |
| Mar 15, 2021 at 14:07 | comment | added | Doc Brown | @yomag1234: "Would that be the correct approach?" - well, if it is "correct" is something you have to evaluate for yourself. But from what you told us so far, I am under the impression it could be a more suitable approach than the current one. Or do you want to keep track of the member variables isSorting, isLeaf, areNodesInit, areNodesSorting, pivotIndex, j i, pivotValue in each of the nodes of the tree? | |
| Mar 15, 2021 at 9:39 | comment | added | yomag1234 | @Caleth I know, but for my purposes I require step-by-step sorting, so I need to save the state in the object until the next time the function is called. | |
| Mar 15, 2021 at 9:23 | comment | added | Caleth | @yomag1234 You may want to look at this SO post Sorts are functions, they traditionally hold state in local variables | |
| Mar 15, 2021 at 8:10 | comment | added | yomag1234 | All right, but I also have another class that uses binary tree, for merge sort also. But merge and quick sort have alot of duplicate code, so I could use inheritance on merge and quick sort classes so they share the duplicated code? And just leave binary tree as "unrelated" composition? Would that be the correct approach? | |
| Mar 15, 2021 at 6:22 | comment | added | Doc Brown | ... of the binary tree. And no, the nodes will not require any additional payload. Your current approach is a pretty good example of how not to use inheritance, and how "composition over inheritance" resolves the issues. | |
| Mar 15, 2021 at 6:21 | comment | added | Doc Brown | @yomag1234: Quicksort, as I know it, uses an array as input and produces an array as output as well. Internally, it processes the array elements in some binary tree order, but that information is usually not kept anywhere. Is your intent to have a Quicksort algo which keeps track of that tree, and keeps track of the internal steps? For this, I would not derive Quicksort from BinaryTree, Quicksort is not a binary tree, but it works on one. By separating the algorithm from the data structure, "Quicksort" can have as many member variables as it requires without interfering with the node members. | |
| Mar 14, 2021 at 18:19 | comment | added | yomag1234 | I've added a concrete derived class to better explain my intent. | |
| Mar 14, 2021 at 17:03 | comment | added | Doc Brown | @yomag1234: I think it is hard to tell what would be most suitable without seeing the actual code. | |
| Mar 14, 2021 at 11:41 | comment | added | yomag1234 | to clarify, now I have derived classes with instance variables and functions required for different tree construction, sorting etc. I should put those in a payload class, and add it to binary tree as a pointer, and also add two other nodes of the payload class? But the derived classes (or the payload) need to know about the other nodes for construction and other functions. I'm confused as to who composites what and what the contents of different classes should be. | |
| Mar 14, 2021 at 10:44 | vote | accept | yomag1234 | ||
| Mar 14, 2021 at 11:34 | |||||
| Mar 13, 2021 at 21:14 | comment | added | Doc Brown | @yomag1234: if your different derived classes don't contain additional members, you don't need any payload. For this case, Robert Harvey's comment is correct, it makes probably no sense to use inheritance at all, just put the different tree constructions in some other class. And Kain0_0's answer then seems to be even more overdesigned than it already is. | |
| Mar 13, 2021 at 15:32 | comment | added | yomag1234 | First off, thank you for an extensive answer.The differences between the different derived classes are the functions for sorting the binary tree, but there are small differences in tree construction as you've speculated.That's one of the parts I've abstracted away using functions in BinaryTree, with specialized templates for the differences, but it's nice knowing template-less approach works just fine. Also I'm not sure what you mean by Payload, if it's the data held by the node, I only need the vector, and I'm not sure how it's superior to use polymorphism only to hold instance variables? | |
| Mar 13, 2021 at 13:35 | history | answered | Doc Brown | CC BY-SA 4.0 |