Lecture 23 - November 14, 2007

Quiz:

Binary fractions:

Pennies.adb

with Ada.Text_IO;
with Ada.Float_Text_IO;
procedure Pennies is

   Three_Pennies : constant Float := 0.03;
   Total_Dollars : Float;

begin
   Total_Dollars := 0.0;                 -- Initialize the sum
   for Count in 1..100_000 loop
      Total_Dollars := Total_Dollars + Three_Pennies;
   end loop;

   Ada.Float_Text_IO.Put (Item => Total_Dollars,
                          Fore => 10,
                          Aft => 2,
                          Exp => 0);
   Ada.Text_IO.New_Line;

   Total_Dollars := 100_000.00 * Three_Pennies;
     Ada.Float_Text_IO.Put (Item => Total_Dollars,
                          Fore => 10,
                          Aft => 2,
                          Exp => 0);
   Ada.Text_IO.New_Line;

end Pennies;

Dollars.adb

Binary Search Trees

Some useful definitions

A binary tree is a tree all of whose nodes have out-degree <= 2.

The subtrees of a binary tree are ordered in the sense that there is a left child and a right

child.

A binary tree is a strictly binary tree iff each of its nodes has out-degree = 0 or out-degree = 2. (i.e. nodes with out-degree = 1 are not allowed in strictly binary trees.

A binary tree is a complete binary tree of depth K iff each node of level K is a leaf and each node of level less than K has nonempty left and right children.

A complete binary tree of depth K always has exactly 2^K+1 nodes.

A tree consisting of a single node has depth = 0.

A binary tree is an almost complete binary tree (ACBT) of depth K iff it is either complete or fails to be complete only because some of its leaves are at the right hand end of level K-1.

An ACBT is useful in heap sort.

NOTE: in the literature, sometimes what is defined above as a complete binary tree is called a full binary tree. When that is the case, what is defined above as an almost complete binary tree is called a complete binary tree.

A binary tree is balanced (sometimes called height balanced) iff for each node in the tree, the depths of the node's right and left subtreees differ by at most one.

A leaf is a node in a tree that has no children

The level of a node is the distance of a node from the root node

The height of a tree is the number of levels in the tree.

A binary search tree is a binary tree in which the key value in every node is greater than the key values in its left subtree and less than the key values in its right subtree.

Look at your assignment 5 programs and see if you can make them bullet proof!

Add a Search and a Delete procedure to your binarySearchTree Program

Read text on Hash and Heap sort

Hash

Heap sort