Inserting value to a sorted binary tree?

This is a discussion on Inserting value to a sorted binary tree? within the C Programming forums, part of the General Programming Boards category; Just read this binary trees explanation (well, read it again, I read it ages ago and forgot it since I ...

  1. #1
    Registered User
    Join Date
    Jan 2008
    Location
    Wexford, Ireland
    Posts
    4

    Inserting value to a sorted binary tree?

    Just read this binary trees explanation (well, read it again, I read it ages ago and forgot it since I don't code much)

    I think I understand it, but I'm not sure about one thing.
    If you have a sorted tree and call insert(X) on the tree, it will find the appropriate location for it(by repeatedly travelling left or right until it finds an empty node, based on whether it's bigger or smaller than current one), and then insert it.
    This should keep the tree sorted (I think anyway), but not balanced (obviously).

    But if I called insert(7) on:
    Code:
        10
       /  \
      7   11
     / \ 
    5   8
    I'd get the 7 being placed to the left of the 8, and the tree would no longer be sorted.
    Is there a way of doing the insertion while keeping the tree sorted or would it just have to be resorted on such occurences?
    (Which I guess wouldn't be too bad considering you'd only really have to resort the tree with root node at 8 AFAICT, not whole thing)

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >I'd get the 7 being placed to the left of the 8, and the tree would no longer be sorted.
    How do you figure that? Run your resulting tree through an in-order traversal and you'll find that it's perfectly sorted:
    Code:
          10
        /    \
       7      11
     /   \ 
    5     8
         /
        7
    The order is 5, 7 (first one), 7 (second one), 8, 10, 11. The duplicate keys don't have to be directly adjacent in the structure. If you did that then you really would violate the binary search tree ordering rule.
    My best code is written with the delete key.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    It's sorted alright. Everything in the direction of the right child of the first seven will come out after it, and everything in the direction of the left child of the 8 will come out before it.

    Not only is it sorted, but if implemented properly, the insertion routine is "stable" in that an item inserted after another item that is equal, will always come out after the first one in an in-order traversal.
    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
    Registered User
    Join Date
    Jan 2008
    Location
    Wexford, Ireland
    Posts
    4
    Ok then I understand now, I was just assuming that duplicates should be connected, looking back at it now I realise that it doesn't seem to make any difference to how it operates.

Popular pages Recent additions subscribe to a feed

Similar Threads

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

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