vitroblue

hello there! i'm vitroblue again with another school proyect (wanna cry) T.T
this time it is about árboles binarios de búsqueda (sorry, i dont know how are they called in english. they are hierarchical data structures and the nodes can only have 0, 1 or 2 children, the ones to the left must have a smaller value than his father and the ones from the right must have a bigger value. is their name a literal translation?)
well, the point is that i have some problems trying to figure out a way to do a search:
i have 3 nodes (*anterior, *actual, *posterior). given any value, let's say 7... a) actual has to be the 7; b) anterior has to be the father and c) posterior has to fall from the tree if 7 does not exist
how do i do this? what should i write in my program? to do this crazy function? i need this in order to make other functions...

nindoja

Please post the current class or struct that you have, then we can help. Also, árboles binarios de búsqueda, sounds like a binary tree. If you google for "binary tree search" you will find a lot of information about trees, searching trees, and probably a solution to your problem. Although you may find a solution, I suggest you read about trees and various searching techniques and try to write your own.

vitroblue

thanks for the name!


but don't think i haven't searched in the web (believe me. in class i just learned which functions it must have and how are they supposed to work. but to write all the binary three class was for homework, so i did it almost all on my own with some web sites help. even in spanish there are plenty of them). but the many examples i found just confused me. they are just to build it up and that's (almost) already done. i know this function is not necesary in a real binary three but as class assingment it has to have all the crazy requests of the teacher (the others were kinda funny ) and this is the only one that i can't do...

DaWei

If I'm understanding you correctly, your node is not constructed in the proper way. A binary tree node contains 1) a value (or reference thereto), 2) a reference to a left child, and 3) a reference to right child. One MIGHT add a reference back to the parent, but it isn't usually done. It appears that you have a reference to the value, a reference to the parent, and a reference to one child.

In a sorted binary tree, the left child is less than the parent and the right child is greater than the parent. If duplicate values are allowed, then one of those relationships needs to be less-or-equal or greater-or-equal. To search, one merely traverses the tree comparing the members against the target value. If the value being sought is less that the value of the current node, one goes left. If it is greater, one goes right. If it is the same, the search has succeeded.

If one needs to remove a value one has to adjust the references of the associated nodes before deleting the node in question. Note in the following tree that the node referencing the value '7' has been removed. Since it was a left child, its left child has been chained to the parent in its place. Its right child has been chained as the right child of the replacement node. If the replacement node (5) had alread possessed a right child, the right chain would have to link into that chain.
If I've misunderstood your question and problem, I apologize.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

vitroblue

well, yeah, i thought i should add a reference to the parent. it would make everything easier but i'm supposed not to do that so all this is caos (coz i may fall from the three and a segmentation fault occurs)... but, thanks!! you have given me a useful idea! i think i can do this in another way... (this assingment is kinda weird) i'll seach just for the value and it's parent in the "while[...]" and if this node has a child to the left (i dont care for the ones at the right), i'll place it in the third node. i think it may work well. lemme try it

DaWei

All you need to do to avoid segmentation faults is to make sure the pointers are valid before you dereference them. In aid of that, initialize the reference pointers to NULL when you make a node, set them to the appropriate reference value when you determine what that is, and set them back to NULL when you break one for relinking purposes. If you don't construct your node properly (two children, for sure, possibly a pointer BACK to the parent), then you'll be reinventing wheels instead of being able to take advantage of the lebenty-zillion previous implementations of the various things one can do with a binary tree. You are no doubt going to progress from wild to sorted binary trees and from there to heaps, etc. I'd suggest you get it down in the beginning.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers