Binary tree search efficiency

This is a discussion on Binary tree search efficiency within the A Brief History of Cprogramming.com forums, part of the Community Boards category; If we're putting these values in a binary tree. 8,7,6,5,4,3,2,1, it will be an ordered tree. It will look like ...

  1. #1
    Registered User
    Join Date
    Sep 2003
    Posts
    5

    Binary tree search efficiency

    If we're putting these values in a binary tree. 8,7,6,5,4,3,2,1, it will be an ordered tree. It will look like an unbalanced tree with all the node on the left side. The search efficiency will be big-Oh(n), right? Well, suppose we have a balance tree. 4 is the root and it's balance. According to my source, the worst code big-Oh is now O(log(n)). How is that? Isn't it Omega(log(n))? Couldn't the worst case for a binary tree still be O(n)? What if in searching the element in a tree is a leaf node all the way at the left-end? The search efficiency would be O(n) woulnd't it, not O(log(n))?

  2. #2
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    8,7,6,5,4,3,2,1 should be just as fast as 1,2,3,4,5,6,7,8

    Way I was taught to figure out what the max number of searches is to take the ceiling value of ( ln(number of values) / ln(2) ).

  3. #3
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    If it is an unbalanced binary tree, O( ln( n ) / ln( 2 ) ) is best-case. Worst case is O( n ).

    If it is balanced, worst case is O( ln( n ) / ln( 2 ) ).
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  4. #4
    Registered User
    Join Date
    Sep 2003
    Posts
    5
    Originally posted by XSquared
    If it is an unbalanced binary tree, O( ln( n ) / ln( 2 ) ) is best-case. Worst case is O( n ).

    If it is balanced, worst case is O( ln( n ) / ln( 2 ) ).
    For worst case, where did ln(2) come from?

  5. #5
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Hmm why do most people use ln x/ln y instead of log x/ log y? The produce the same results. Interesting, very interesting

  6. #6
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916
    Originally posted by Thantos
    Hmm why do most people use ln x/ln y instead of log x/ log y? The produce the same results. Interesting, very interesting
    Properties of logarithms. Check out the logarithm change of base rule. It's on line 15 of this page It will answer the last two questions.

    The ln(2) comes from a base 2 logarithm.
    Away.

  7. #7
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    thanks for the link.

  8. #8
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Location
    Mt. Prospect, IL
    Posts
    2,572
    Originally posted by confuted
    Properties of logarithms. Check out the logarithm change of base rule. It's on line 15 of this page It will answer the last two questions.

    The ln(2) comes from a base 2 logarithm.
    Yes, but in time analysis the base of a log is irrelevant really.

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  9. #9
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916
    Originally posted by axon
    Yes, but in time analysis the base of a log is irrelevant really.
    It changes the value of the log. In this case, it gives you the multiplier (1/ln(2)), so it's kinda important...
    Away.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. BST (Binary search tree)
    By praethorian in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2005, 08:11 AM
  2. Binary Tree Search
    By nickname_changed in forum C++ Programming
    Replies: 7
    Last Post: 01-12-2004, 11:40 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. Binary Search Tree, Inserting node
    By cheryl_li in forum C Programming
    Replies: 1
    Last Post: 09-13-2003, 03:53 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21