Date: Mon, 27 Nov 2006 14:22:39 -0600 (CST) From: Mark Jacobson To: 810-080-02-FALL@uni.edu Subject: Test three on FRIDAY... Hi 080 students, Test is on this Friday instead of being on this Wednesday. ------ We reviewed POSETs(r, a and t), equivalence relations (r, s and t), hash tables, floor and ceiling and log to the base 2 function, composition of functions, binary search trees and calculating successful search performance today to hash tables and bst's, and calculating unsuccessful search performance for hash tables too. We did preorder and inorder and postorder traversals of binary search trees today again too. Can you create a bst (binary search tree) from just the preorder --- - - - or postorder traversal output? If the pre or post output is output of the SEARCH KEY values, you do NOT need the INORDER traversal output. You already know what it is! There is a handout from today's class you want to be sure to get on Wednesday during class. rst binary relations are equivalence relations. art binary relations are POSETs, which stands for Partially Ordered Sets. The <= binary relation on the Integers or the Naturals is the classic example of a POSET, but the subset relation is another example too. The <= relation is actually called a TOTAL ORDER, cause every natural number pair m and n where m is not equal to n has the property that m <= n OR n <= m But for the powerset of { u, n, i } and the subset relation, {u} is not a subset of {n, i} and {n, i} is not a subset of {u}, which means the two elements of the PowerSet of { u, n, i } are NOT related, which means it is a PARTIAL ORDERING, a POSET, and it is NOT a Total Order, like the Naturals or Integers and the <= binary relation on them. Mark