Results 1 to 4 of 4

Thread: balanced Binary Search Tree has search O(log(n))

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    35
    Thanks
    1

    balanced Binary Search Tree has search O(log(n))

    Why does a well balanced Binary Search Tree have a search complexity of O(log(n)), if you search for one element?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,574
    Thanks
    789

    Re: balanced Binary Search Tree has search O(log(n))

    The idea is that the height (and, therefore, the number of comparisons to make) of such tree must be approximately log(n) where n is the number of leaves. For more information, could you remind the definition of well-balanced and other details, such as whether you store data in leaves only or also in the internal nodes?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2011
    Posts
    35
    Thanks
    1

    Re: balanced Binary Search Tree has search O(log(n))

    I think a "well balanced tree" is one that has a fairly equal distribution of nodes, if that makes sense.

    Leaf nodes: Nodes with no children
    Interior nodes: Nodes with children
    Any node can be considered the root of a subtree.

    A tree consists of a collection of nodes connected by directed arcs.
    Path length: the number of arcs tranversed
    height: the maximum path length from that node to the leaf node
    depth: the path length from one root to that node
    - root node has a depth of 0
    - a tree's depth is the max depth of all its leaf nodes (which is also the tree's height)

    Binary Tree:
    -nodes have no more than two children
    -children are generally referred to as "left" and "right"

    Full Binary Tree:
    - every leaf is at the same depth
    - every internal node has 2 children
    - height of h will have 2^{h+1}-1 nodes
    - height of h will have 2^{h} leaves

    Complete binary tree: full except for the bottom level which is filled from left to right.

    Binary search trees are binary trees where every node value is:
    -greater than all its descendants in the left subtree
    -less than or equal to all its descendants in the right subtree
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,574
    Thanks
    789

    Re: balanced Binary Search Tree has search O(log(n))

    Thanks for the definitions.

    Quote Originally Posted by over9000 View Post
    I think a "well balanced tree" is one that has a fairly equal distribution of nodes, if that makes sense.
    The proof that a search complexity is O(log(n)) can only be as precise as the definition of "well-balanced". You also did not say whether information is stored in leaves only or also in internal nodes. The precise bounds are slightly different, but the O(log(n)) estimate is the same in both cases.

    For example, if you store information in leaves and "well-balanced" means "complete", then the number n of leaves (and pieces of data) is greater than 2^(h-1) (the number of nodes on the second last level) where h is tree's height. Taking log₂, we get log(n) > h - 1, or h < log(n) + 1. Since search complexity is proportional to tree's height, the complexity is O(log(n)).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: Jul 17th 2013, 11:28 AM
  2. search For f - 1
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: Oct 28th 2007, 06:11 PM
  3. Binary Search Algorithm
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Nov 11th 2006, 10:57 PM

Search Tags


/mathhelpforum @mathhelpforum