Finding the Root of a Complete Tree

This is a discussion on Finding the Root of a Complete Tree within the C++ Programming forums, part of the General Programming Boards category; Find the element that will serve as the root element of a complete binary search tree. Give the index. I ...

  1. #1
    Registered User
    Join Date
    Sep 2004
    Posts
    15

    Finding the Root of a Complete Tree

    Find the element that will serve as the root element of a complete binary search tree. Give the index. I just need help finding the mathematical equation for this.

  2. #2
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    Okay there are some things that are assumed here, for instance it is assumed that the data is in some particular format to begin with. Since your instructor asked for an index, I will guess that the data is in an array. So you need to figure out which element in the array will be the root element in the tree, and return the index. Now, ANY element could be the root, it really doesn't matter, so is the question really asking, "what is the ideal element for the root of the tree assuming 'ideal' means balanced?" And finally, you can ask yourself, if I want a balanced tree, what IS a good choice for a root element? Is it the smallest value? The largest? Does it matter? Why?
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    If I'm not mistaken, but doesn't a complete binary search tree have only one possibility for the root? I forget what the mathematical term for it is but I would think the root is always the number thats the middle of the of numbers, in other words the only number that has X items greater than it and X items less than it.

    I don't think theres a mathematical equation for it though since the values could be heavily skewed for example the array [2,1,10000000] the root would be 2 but I don't know how you would come up with that with an equation. A simple algorithm could do it though.

  4. #4
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Quote Originally Posted by IfYouSaySo
    Now, ANY element could be the root, it really doesn't matter,
    What? In a 'complete' binary search tree, the root does matter. Given any ordering of elements, there is only one way to make a complete binary search tree.

    Mr. Acclude, I believe your effort to figure out your calculation can be simplified with these questions, all directly calculable from the total number of elements.

    1. How many elements will be in the bottom row of a tree of size N?
    2. How many elements (in the bottom row) will lie to the left of the center of the tree?
    3. How many elements won't be in the bottom row of the tree? Of these how many are left of center?

  5. #5
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    My mistake. 'Complete' basically means 'balanced'. It's probably a more strict definition actually. At any rate the choice is the middle element. I was going to let him figure that out, since it is homework and all, but whatever.
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  6. #6
    Registered User
    Join Date
    Sep 2004
    Posts
    15
    No it's homework, teacher said to go think about it, and I was wondering and couldn't figure it out. And yea your right a algorithm not a equestion.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Templated Binary Tree... dear god...
    By Nakeerb in forum C++ Programming
    Replies: 15
    Last Post: 01-17-2003, 02:24 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 11:45 PM

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