Binary tree question

This is a discussion on Binary tree question within the C++ Programming forums, part of the General Programming Boards category; As i am understanding, if you delete the root node of a binary tree, there are two ways to re-order/re-connect ...

  1. #1
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149

    Binary tree question

    As i am understanding, if you delete the root node of a binary tree, there are two ways to re-order/re-connect the data. Left promotion and Right promotion.
    Could someone check to see if this is correct.

    Code:
                                                           10
    						     /    \
    						    6      14
    						   / \    /  \
    						  5   8  11  18
    Here is how i'm thinking it works.
    If i delete the root 10, and use left promotion...
    the right subtree would move under 8 to the right?
    Code:
                   6
                 /   \
                5     8
                       \
                        14
                       /  \
                      11  18
    and if it is right promotion and i delete 10 it moves the left subtree under the 11
    and would be:
    Code:
                   14
                  /  \
                 11  18
                 /
                6
               / \
              5   8
    is this correct?

  2. #2
    Registered User
    Join Date
    Jan 2007
    Posts
    40
    google "reheapification for binary trees"

    don't remember all the properties off the top of my head, but both of your reheapifications look correct. Keep in mind that whether you use left subtree reheapification or right subtree reheapification it could affect algorithm performance based on whether you're useing inorder, preorder, postorder processing...

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,293
    Quote Originally Posted by brooksbp View Post
    google "reheapification for binary trees"

    don't remember all the properties off the top of my head, but both of your reheapifications look correct. Keep in mind that whether you use left subtree reheapification or right subtree reheapification it could affect algorithm performance based on whether you're useing inorder, preorder, postorder processing...
    Look closer, they are not correct.

    Using left-propotion you would get:
    Code:
               8
             /   \
           6      14
          /      /  \
         5      11  18
    And for right...
    Code:
              11
             /   \
           6      14
          / \      \
         5   8     18
    The promoted node becomes the root, by means of replacing the old root with the promoted node. You don't just cut the left half of the tree off and plonk it on at the top.
    Last edited by iMalc; 05-03-2007 at 03:29 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    A valuable resource is Prelude's web-site.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. best STL method to implement a binary tree
    By MatthewDoucette in forum C++ Programming
    Replies: 8
    Last Post: 06-16-2006, 07:08 AM
  3. BST (Binary search tree)
    By praethorian in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2005, 08:11 AM
  4. Templated Binary Tree... dear god...
    By Nakeerb in forum C++ Programming
    Replies: 15
    Last Post: 01-17-2003, 01:24 AM
  5. inserting characters into a binary tree
    By sballew in forum C Programming
    Replies: 4
    Last Post: 12-06-2001, 03:08 PM

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