1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

CS: heaps and binary trees

  1. Apr 27, 2010 #1
    I have been given a practice exam from my professor (http://www.cs.pitt.edu/~aronis/cs0445/miscellaneous/cs445-spring-2007-test-3.pdf [Broken]) along with an answer sheet (http://www.cs.pitt.edu/~aronis/cs0445/miscellaneous/cs445-spring-2007-test-3-answers.txt [Broken]) and there are a good number of questions on heaps and binary trees. Unfortunately, he's a pretty bad professor and never exactly "showed us" how to add/remove to/from a heap or a binary tree. I'm looking for a good "visualization" of how to do this, and googling hasn't gotten me very far. If anyone has a web page or even notes from your own class on adding and removing from these data structures, it would be greatly appreciated.

    Thanks!
     
    Last edited by a moderator: May 4, 2017
  2. jcsd
  3. Apr 28, 2010 #2

    Filip Larsen

    User Avatar
    Gold Member

    In "Algorithms", Robert Sedgewick uses around 10 pages to describe and visualize the heap structure and operations. I would recommend that book (or one of his language specific editions) for any CS book shelf.
     
  4. Apr 28, 2010 #3
    deleting from a binary search tree:

    case 1: the node you want to delete ( the node with 7 ) has 1 child:

    Code (Text):

       6
    5    7
            8
     
    solution: disconnect it from the tree by directly linking 7's only child to the node above

    Code (Text):

       6
    5     8
     
    case 2: the node you want to delete has no children (say, 7 again)

    Code (Text):

       6
    5     7
     
    solution: this case is trivial, just delete it off

    Code (Text):

       6
    5
     
    case 3: the node you want to delete has 2 children (7 again):

    Code (Text):

         5
            7
         6     8
     
    solution: Find its successor node (next node in a sorted order), copy it up to 7's position

    Code (Text):

         5
            8
         6     8
     
    now delete 8 from the subtree mainroot.right.right with one of the cases above

    final:

    Code (Text):

         5
            8
         6    
     
    notice how in the 2 children case (case 3), when deleting the successor node from the respective subtree, you will always end up doing case 1 or 2 again (the "easy" cases)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: CS: heaps and binary trees
  1. Binary trees (Replies: 1)

  2. Binary Search tree (Replies: 5)

Loading...