Fundamentals of OOP and Data Structures in Java - Part5

Couple of Days back i started reading Fundamentals of OOP and Data Structures in Java By Richard Wiener and Lewis J. Pinson

Below are few quotations i found from this book from the next 3 chapters (14-15-16).

1) Trees are our first example of a nonlinear structure for containing objects. Although conceptually more complex than linear data structures,trees offer the opportunity for improved efficiency in operations such as inserting, removing, and searching for contained objects. Heaps are also nonlinear in structure and contained objects must be organized in agreement with an order relationship between each node and its descendants. A heap may be efficiently implemented using a binary tree. A priority queue is a special kind of queue that contains prioritized objects (usually based on a key) in a way that the objects are removed based on their priority (highest priority first). Priority queues may be implemented using a heap.There is a nonessential but beneficial relationship among these three data structures; that is why they are grouped together in this chapter. Additional variations on binary trees are covered in later chapters.

2) A tree is a nonlinear data structure that derives its name from a similarity between its defining terminology and our friends in the forest, real trees. A tree data structure is considerably more constrained in its variety than a real tree and is typically viewed upside down, with its root at the top and leaves on the bottom. A tree is usually accessed from its root,then down through its branches to the leaves.

3) A tree is a nonlinear structure composed of nodes. A tree is accessible only through a special node called the root.

4) A BinaryTree is a tree whose nodes have at most two descendant trees as offspring. A BinaryTree is characterized by queries for traversing its nodes and for measuring average path length.

5) A perfectly balanced binary tree has a unique logarithmic relation of its height to the number of nodes it contains. The average path length for a perfectly balanced binary tree is approximately equal to one less than its height.

6) A binary expression tree is a binary tree that represents binary expressions. An expression tree is easily built from a postfix form of the expression it represents. Traversals of an expression tree produce the prefix, infix, and postfix strings for the represented expression.

7) A heap is a complete binary tree whose nodes satisfy the heap-ordering property, that the contents of any node is no larger than the contents of any of its descendant nodes. A heap may also be designed as a linear indexable list. A heap also has the property that it may be used for efficient sorting.

8)A priority queue is a special queue that contains prioritized objects. Since its objects must be Comparable, a PriorityQueue has behavior consistent with a SearchTable. It has the property that the next value removed is always highest priority. A priority queue may be implemented using a heap or a linear structure

9) A binary tree holds the generic Object type that serves as a placeholder for any reference type. This combined with its nonlinear structure makes it suitable for representing a diversity of information.

10) Binary Search Tree

A binary search tree is a specialized type of binary tree. In order for the tree to qualify as a binary search tree, each of its nodes must satisfy the following two conditions:

a. All elements in its left subtree must have key values smaller than the key value of the node.
b. All elements in its right subtree must have key values larger than the key value of the node.

11) Hash tables and sets are containers and share the common property that duplicates are not allowed. Hashing may be used in the implementation of a set. Major points made about hashing and sets are:

12) Hashing is the process of calculating an integer index to represent an object. This object may then be stored in a hash table at the hashed index. The ratio of objects in a hash table to its capacity is called its "load factor."

13) A perfect hashing operation produces a unique index for all objects it hashes: The index is uniformly distributed over the range of indices in the hash table. A hash table with a perfect hashing function can theoretically have a load factor of one.

14) The craft of designing hash functions falls far short of the ideal hashing function desired. As a result, practical hashing functions sometimes cause collisions.

15) A collision occurs when two different objects hash to the same index. Reducing the load factor of a hash table may reduce the relative frequency of collisions.

16) There are several algorithms for resolving collisions. These include linear chaining, coalesced chaining, and separate chaining among others.

17) The ideal performance of a hash table is O(1). This performance is degraded because of collisions and the need to resolve those collisions.

18) Coalesced chaining provides better performance than linear chaining.


About the Author

Richard Wiener is Associate Professor of Computer Science at the University of Colorado at Colorado Springs and Editor-in-Chief of The Journal of Object-Oriented Programming. He is the author or co-author of twenty-one textbooks and professional books. In 1983 Richard Wiener received the Outstanding Teacher of the Year Award from the University of Colorado at Colorado Springs. His areas of research include object-oriented software development,simulated annealing and genetic algorithms, time series, and applied statistics.

Lewis J. Pinson is President of CIC and Associate Professor of Computer Science at the University of Colorado at Colorado Springs. His areas of expertise include computer software development, object-oriented problem solving,genetic algorithms, and complexity studies. He develops and presents training courses and intensive short courses and workshops on object-oriented problem solving and object-oriented languages. Dr. Pinson has authored or co-authored eight books.