deletion from AVL tree where both child nodes are internal

This is a discussion on deletion from AVL tree where both child nodes are internal within the Tech Board forums, part of the Community Boards category; In the picture how would node with key 2 be deleted from an AVL tree? The rule I know is ...

  1. #1
    Registered User
    Join Date
    Apr 2010
    Location
    Vancouver
    Posts
    116

    deletion from AVL tree where both child nodes are internal

    In the picture how would node with key 2 be deleted from an AVL tree? The rule I know is replace it with the right subtree's left most child, but but 3 doesn't have a left child. I can't replace 2 with 4 b/c 3<4 so do I replace 2 with 3?
    Name:  bstree.png
Views: 437
Size:  2.9 KB

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,491
    The right subtree's left-most child is not quite accurate. It's actually the smallest node in the right subtree. A completely valid alternative is the largest node in the left subtree. The smallest node in the right subtree is the right subtree's root, i.e. the 3 node.

  3. #3
    Registered User
    Join Date
    Apr 2010
    Location
    Vancouver
    Posts
    116
    Thanks

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. total nodes in a tree
    By BEN10 in forum C Programming
    Replies: 5
    Last Post: 01-10-2010, 10:37 AM
  2. Binary Tree - sum of nodes
    By Tiffanie in forum C++ Programming
    Replies: 1
    Last Post: 09-15-2008, 08:49 AM
  3. Binary tree not inserting nodes correctly
    By jk1998 in forum C++ Programming
    Replies: 7
    Last Post: 09-22-2007, 12:37 PM
  4. Binary Search Tree deletion
    By gflores in forum C++ Programming
    Replies: 2
    Last Post: 09-23-2005, 06:01 PM
  5. number of nodes in tree
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 04-24-2002, 06:49 AM

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