I think i am gonna need some help... feeling retarded :\

[Elledan]

<< Elledan - like said, it's a data structures thing. As I said earlier, it's a binary tree (each node has only two children) with the condition that all descendents that are smaller than the parent node fall to the left and all larger to the right when the tree is made. When the tree is searched, the first node (the root node) is compared with the search value - if the value being searched for is smaller than the root node, the search continues down the left side of the tree. It gets to the next node (which by definition is smaller than the previous node, the root node in this case). It is then compared to this current node and lets say it is larger than the current node. It then goes to the next node to the right of the current node because it was larger. This continues until the search finds what it's looking for or you run out of nodes. This can be done using linked lists, each node having a reference to &quot;left&quot; and &quot;right&quot;... >>


You know what? I perfectly understand what you're saying

Now I only have to know how to go about implementing this in a program

 

[hans007]

well if the tree is a full set of nodes, then it has 2^n-1 nodes.


n being the height i think. So... if i recall, say it has 15 nodes then its

15=2^n-1 so 16=2^n and n is 4


if you only knew the number of nodes on the bottom level then, you can find out the number of nodes total. if its a full tree, than the nodes at the bottom are half the nodes in the whole tree plus 1.


so if there are 16 nodes then there are 15 other nodes above it.

1
2
4
8
16

right


so you just go bottonnodes *2 +1 = 2^n and find out n again, n is 5 in that case


if you dont have a full tree, you just implement a recursive algorithm that iterates until it finds null node pointer. Youjust have each instance of the function use the current length as a parameter. then you add one until you hit the leafs, and when you are returning the length finally when you hit a leaf one, you compare the left and the right nodes on each step above the leaf nodes, and return the greater one.

 

[ThisIsMatt]

<< You know what? I perfectly understand what you're saying >>

Well ya know, I did get a B- in the class So you see how they can be somewhat faster than linear searching

 

[pen^2]

lol@TripleJ, i am easily amused tonite

 

[Elledan]

<<

<< You know what? I perfectly understand what you're saying >>

Well ya know, I did get a B- in the class So you see how they can be somewhat faster than linear searching >>

'Somewhat faster'? I'd imagine that especially with many items to search from, like a huge array with 2^20+ numbers, it would speed things up a bit

 

[ThisIsMatt]

Elledan - why don't you ask Pen^2 about AVL trees and B-trees too...have him explain the balancing with single and double rotation. While your at it, might as well learn about Red Black trees too, they're my favorite I'm sure he'd be glad to answer anything about them...as for me, I'm going to bed

laters

 

[Elledan]

Maybe I'll ask him later when I finally get rid of this headache

 

[pen^2]

dont ask! i am here to ask a question, not to answer

 

[Elledan]

<< dont ask! i am here to ask a question, not to answer >>

Damn, now I'll have to look for someone else to bother with annoying questions