Previous | Table of Contents | Next |
1.2.19.6. Trees
An efficient sorting program can be constructed using a data structure that is a binary tree. The resulting program, tree_sort, has an expected running time proportional to n log2 n.
It is quite difficult to write nonrecursive programs to process trees, so we will think of trees as recursive structures. Using this approach, a binary tree of integers is either empty or an integer, followed by two binary trees of integers, called the left subtree and right subtree.
Sorting with Trees
To sort numbers with a tree, we will construct a special kind of ordered binary tree with the property that the number at the top or root node of the tree is greater than all the numbers in its left subtree and less than or equal to all the numbers in its right subtree. This property will hold not only for the most accessible node at the top of the tree, but for all nodes of the tree.
The sorting process consists of inserting the values to be sorted, one at a time, into the tree (after starting with and empty tree) and then printing the values in the tree in the correct (infix) order.
Type Declarations for Trees
The declaration for the node of a tree must contain two pointers, one to the left subtree and
type, public :: node integer :: value type (node), pointer :: left, right end type node
The subroutine that inserts a new number into the tree is a straightforward implementation of the following informal recipe: If the tree is empty, make the new entry the only node of the tree; if the tree is not empty and the number to be inserted is less than the number at the root, insert the number in the left subtree; otherwise, insert the number in the right subtree.
The recipe for printing the nodes of the tree follows from the way the tree has been built: It is simply to print in order the values in the left subtree of the root, print the value at the root node, and then print in order the values in the right subtree. This subroutine is shown in the following complete module and program that sort a file of integers by reading them all in, constructing an ordered binary tree, and then printing out the values in the tree in order:
module tree_module public :: insert, print_tree type, public :: node integer :: value type (node), pointer :: left, right end type node contains recursive subroutine insert (t, number) type (node), pointer :: t ! A tree integer, intent (in) :: number ! If (sub)tree is empty, put number at root if (.not. associated (t)) then allocate (t) t % value = number t % left => null () t % right => null () ! Otherwise, insert into correct subtree else if (number < t % value) then call insert (t % left, number) else call insert (t % right, number) end if end subroutine insert recursive subroutine print_tree (t) ! Print tree in infix order type (node), pointer :: t ! A tree if (associated (t)) then call print_tree (t % left) print *, t % value call print_tree (t % right) end if end subroutine print_tree end module tree_module program tree_sort ! Sorts a file of integers by building a ! tree, sorted in infix order. ! This sort has expected behavior n log n, ! but worst case (input is sorted) n ** 2. use tree_module type (node), pointer :: t ! A tree integer :: number, ios t => null () ! Start with empty tree do read (unit = *, fmt = *, iostat = ios) number if (ios < 0) then exit end if call insert (t, number) ! Put next number in tree end do ! Print nodes of tree in infix order call print_tree (t) end program tree_sort
The input/output statements are
The read, write, and print statements are the ones that do the data transfer; the open and close statements deal with the connection between an input/output unit and a file; the inquire statement provides the means to find out things about a file or unit; and the backspace, endfile, and rewind statements affect the position of the file.
Input and output operations deal with collections of data called files. The data in files are organized into records, which may correspond to lines on a computer terminal, lines on a printout, or parts of a disk file. The descriptions of records and file are to be considered abstractions and do not necessarily represent the way data is stored physically on any particular device.
Previous | Table of Contents | Next |