avl tree delete question

This is a discussion on avl tree delete question within the C++ Programming forums, part of the General Programming Boards category; Hi, when I delete a node in the tree should I call the rebalance function for the node that takes ...

  1. #1
    nik
    nik is offline
    Registered User
    Join Date
    Nov 2010
    Posts
    44

    avl tree delete question

    Hi,

    when I delete a node in the tree should I call the rebalance function for the node that takes the place of the deleted node or for the parent of the deleted node?

    thanks in advance

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by nik View Post
    Hi,

    when I delete a node in the tree should I call the rebalance function for the node that takes the place of the deleted node or for the parent of the deleted node?

    thanks in advance
    The depends on whether the removal of that node from where it was, caused the height of the subtrees of where it was moved to, to differ by two. If not then no, if it did then yes.

    There are easy ways to find out on your own too. You could not call it and then call a validation routine to see if the height properly is still correctly maintained, or you could call it and see if any rotations occur.
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Delete all from a Binary Tree
    By Silvio in forum C Programming
    Replies: 5
    Last Post: 04-25-2009, 07:23 AM
  2. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 06:59 PM
  3. Question about delete
    By Phoenix_Rebirth in forum C++ Programming
    Replies: 4
    Last Post: 09-23-2007, 12:28 PM
  4. Binary tree question
    By Cpro in forum C++ Programming
    Replies: 3
    Last Post: 05-03-2007, 08:08 AM
  5. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM

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