Thread: quick question of a binary search tree child nodes

  1. #1
    Registered User
    Join Date
    Apr 2019
    Posts
    650

    quick question of a binary search tree child nodes

    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
    quick question of a binary search tree child nodes-binary-tree-export-jpg

    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

  2. #2
    Registered User
    Join Date
    Apr 2019
    Posts
    650
    all so what happens if the computer guess's a number that isn't a child node of the level your at.

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,213
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,844
    Quote Originally Posted by cooper1200
    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.

    Quote Originally Posted by cooper1200
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Apr 2019
    Posts
    650
    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

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,844
    No. It depends on order of insertion, and is why a simple binary search tree can become imbalanced.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,813
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 03-08-2012, 06:12 PM
  2. Question about computing the number of nodes in a Binary Tree
    By Overworked_PhD in forum C Programming
    Replies: 3
    Last Post: 12-12-2009, 01:10 PM
  3. Replies: 2
    Last Post: 12-01-2007, 10:44 PM
  4. Binary Search Tree - one last question
    By tms43 in forum C++ Programming
    Replies: 2
    Last Post: 11-14-2006, 03:58 AM
  5. deleting all nodes of a binary search tree...
    By sachitha in forum C++ Programming
    Replies: 3
    Last Post: 09-29-2004, 06:19 AM

Tags for this Thread