quick question of a binary search tree child nodes

[cooper1200]

im reading the section on binary search trees in the book c unleashed pages 458 and 459 have me confused. for those that don't have the book it describes a guessing game where the computer guesses a number between 1 and 15 and the user tells the computer if it guessed right or if the guess was too high or too low.

it then shows a binary search tree that demonstrates this. it stipulates that from the parent node the value of the child node to the left must be less than the parent node and the child node to the right must be greater than the parent.

it then gives the following two examples


please excuse the bad drawings hopefully it has embedded them.

i can see that in each example all the values to the left of the top node are less than the top node and all the ones to the right are greater than the top node.

the question arises how does one decide what values go where and why would one do this the guessing game could easily be written with an if else statement in a loop.

coop

[cooper1200]

all so what happens if the computer guess's a number that isn't a child node of the level your at.

[Salem]

1->2->3->4->5->6->7->8->9->10->11->12->13->14->15
An ordered linked list is also a binary tree. All the left-nodes are empty.
It's a rubbish tree, because it's nowhere near balanced.
It's depth is 15, whereas your perfectly balanced first example only has a depth of 4.

Balancing is important for searching, as that minimises the amount of searching that needs to be done.

> the question arises how does one decide what values go where
You said it yourself in your previous sentence.
If X is less than the current node, you go left.
If X is greater than the current node, you go right.

> and why would one do this the guessing game could easily be written with an if else statement
Because it's meant to illustrate a point in an accessible form that you might understand.
It's to show you how a tree works, not how to implement a guessing game.
A more complicated game (like chess) has a much bushier tree, with many more levels.

[laserlight]

how does one decide what values go where

By searching the tree to find the position to insert a node with the new value such that it satisfies the binary sesrch tree conditions.

why would one do this the guessing game could easily be written with an if else statement in a loop.

Assuming the binary search tree is balanced, it will only take log n comparisons on average to find the number or decide that it doesn't exist, whereas linear search will take n/2 comparisons on average, given that there are n items to search. You could sort and then use binary search for similiar time complexity, but this binary search tree is an alternative to that approach.

[cooper1200]

sorry i dont think i asked the right question i get smaller values to the left and larger values to the right but is each parent node supposed to be range between smallest possible number and the top parent / 2 for the left hand side and some other calculation for the right hand side?
coop

[laserlight]

No. It depends on order of insertion, and is why a simple binary search tree can become imbalanced.

[Click_here]

Self-balancing binary search tree - Wikipedia

As you add data to a tree it can go from the first example you gave to something more unorganised - this means that searching becomes slower. To overcome this different strategies are implemented when inserting a new item (such as Red/black tree Red–black tree - Wikipedia).

Imagine the difference between a balanced tree and imbalanced tree with thousands of items