CSC 216/s08/do right: Difference between revisions

From Expertiza_Wiki
Jump to navigation Jump to search
 
(16 intermediate revisions by 2 users not shown)
Line 1: Line 1:
Special Notes about Binary Search Trees
[[Image:Binary_search_tree.png|left|250px|thumb||This is an example of a binary search tree]]
# the left subtree of a node contains only values less than the node's value;
# the right subtree of a node contains only values greater than or equal to the node's value.
===Formatting Resources===
===Formatting Resources===
[http://meta.wikimedia.org/wiki/Help:Wikitext_examples Formatting Help Guide from MetaWiki]
[http://meta.wikimedia.org/wiki/Help:Wikitext_examples Formatting Help Guide from MetaWiki]
Line 7: Line 11:
===The problem===
===The problem===


Teaching the students how to insert and delete nodes from Binary Search Tree.  
Teaching the students how to '''insert''' and '''delete''' nodes from Binary Search Tree.  
<br>This includes:
<br>'''Insertion'''
<br>How do we do insertion in a binary tree?
<br>Insertion begins as a search would begin; if the root is not equal to the value, we search the left or right subtrees as before. Eventually, we will reach an external node and add the value as its right or left child, depending on the node's value. In other words, we examine the root and recursively insert the new node to the left subtree if the new value is less than the root, or the right subtree if the new value is greater than or equal to the root.
<br>How do we delete a node from a binary search tree?
<br>'''Deletion
     •If the node is a leaf node, then _______________?
'''
     •If the node has one child, modify ______________?
<br>There are several cases to be considered:
     •If the node has two children, __________________?
     * Deleting a leaf: Deleting a node with no children is easy, as we can simply remove it from the tree.
     * Deleting a node with one child: Delete it and replace it with its child.
     * Deleting a node with two children: Suppose the node to be deleted is called N. We replace the value of N with either its
      in-order successor (the left-most child of the right subtree) or the in-order predecessor (the right-most child of the left
      subtree).


===Participants and props===
===Participants and props===


Students can do this on their individual computers or on in groups. Only thing that is needed from the users computer is flash loaded on it.
Students can do this on their individual computers or on in groups. Only thing that is needed from the users computer is flash loaded on it.
[http://people.engr.ncsu.edu/efg/216/s08/video/t3/BinaryTree.swf Flash link Click Here]


===The script===
===The script===


Watch an interactive flash video insert and remove nodes from a binary search tree. Participate with the video by deciding how a binary search tree would look after adding or removing a node from the tree.
Video animation, teaches students how to insert and delete from a binary search tree from the different cases mention above. This flash animation also has a built in game that allows players to insert and remove nodes from a binary search tree.

Latest revision as of 19:03, 6 November 2008

Special Notes about Binary Search Trees

This is an example of a binary search tree
  1. the left subtree of a node contains only values less than the node's value;
  2. the right subtree of a node contains only values greater than or equal to the node's value.

Formatting Resources

Formatting Help Guide from MetaWiki

Learning how Binary Search Tree Works

The problem

Teaching the students how to insert and delete nodes from Binary Search Tree.
Insertion
Insertion begins as a search would begin; if the root is not equal to the value, we search the left or right subtrees as before. Eventually, we will reach an external node and add the value as its right or left child, depending on the node's value. In other words, we examine the root and recursively insert the new node to the left subtree if the new value is less than the root, or the right subtree if the new value is greater than or equal to the root.
Deletion
There are several cases to be considered:

   * Deleting a leaf: Deleting a node with no children is easy, as we can simply remove it from the tree.
   * Deleting a node with one child: Delete it and replace it with its child.
   * Deleting a node with two children: Suppose the node to be deleted is called N. We replace the value of N with either its 
     in-order successor (the left-most child of the right subtree) or the in-order predecessor (the right-most child of the left 
     subtree).

Participants and props

Students can do this on their individual computers or on in groups. Only thing that is needed from the users computer is flash loaded on it.

Flash link Click Here

The script

Video animation, teaches students how to insert and delete from a binary search tree from the different cases mention above. This flash animation also has a built in game that allows players to insert and remove nodes from a binary search tree.