Thread: Newbie binary tree confusion

  1. #1
    Registered User Sharke's Avatar
    Join Date
    Jun 2008
    Location
    NYC
    Posts
    303

    Newbie binary tree confusion

    I'm just learning about binary trees in my C text, specifically the part about deleting nodes with two children. In the example code it gives, the left side of the deleted node is attached to the parent of the deleted node, then the right side of that subtree is traversed in order to find a spot to reattach the right side of the deleted node.

    Does it matter which side of the deleted node is reattached to the parent? The text uses a deletion of a node which is attached to the left side of its parent as an example and the example code follows from this. But I presume that this code also applies to the case in which the deleted node is attached to the right side of its parent. In other words, does it matter what physical "shape" your tree ends up in (its imaginary shape anyway), as long as it's technically correctly ordered, i.e. everything on the correct side of everything else?

    I guess I was expecting the side of initial reattachment to depend on whether the deleted node was attached to the right or left of its parent, and was surprised to see that the code given picked one way of doing it over the other for both cases.

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Some code might pick between the next greatest or next smallest at random, but yes most implementations just always go one way.
    It simply doesn't matter which you choose though. The only time you ever care about the tree shape upon deletion is when you're using a type of self-balancing binary tree. Even then though, the shape upon deletion is taken care of by other means.
    If you're using an ordinary binary tree then the effect of deletions on performance is the least of your worries.
    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"

  3. #3
    Registered User Sharke's Avatar
    Join Date
    Jun 2008
    Location
    NYC
    Posts
    303
    Quote Originally Posted by iMalc View Post
    Some code might pick between the next greatest or next smallest at random, but yes most implementations just always go one way.
    It simply doesn't matter which you choose though. The only time you ever care about the tree shape upon deletion is when you're using a type of self-balancing binary tree. Even then though, the shape upon deletion is taken care of by other means.
    If you're using an ordinary binary tree then the effect of deletions on performance is the least of your worries.
    Thanks, that's cleared things up for me.

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, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM