CST370 - Week 6

CST370-30_2252: Design & Analysis of Algorithms – Week 6

The Lecture this week covers a variety of terms, starting with the AVL tree and the 2-3 tree. A binary search tree must be balanced to enhance the time efficiency for searching, insertion, and deletion. The AVL tree represents a self-balanced structure that preserves the average time complexity of a BST to the Ꝋ(log n). The main property of the AVL tree is that the difference between the right and left subtree heights must be 0 or +1 or −1 at any node. Rotation techniques (R, L, LR, RL) are used to rebalance the AVL trees in the case of insertion or deletion. 

A 2-3 Tree data structure with 2 children and one data element or 3 children with 2 data elements

Another structure that can be used to balance BST is the 2-3 tree. The tree could have two nodes for a single key K and two children: the left subtree with keys less than K and the right subtree with values greater than K.  Another type of 2-3 tree is the 3-node with two key values K1, and K2 (K1 < K2). The 3-node has three children: the left subtree contains key values less than K1, a middle child with key values between K1 & K2, and the right child that holds all key values greater than K2. One of the properties of 2-3 trees is that leaves are the same height. We also reviewed inserting a key value in 2-3 trees.  For the worst and average case, the time complexity for searching, insertion, and deletion is Ꝋ(log n).

The module introduces the Heap data structure as an efficient method of processing priority queue operations. There are two essential conditions for a Max Heap structure: 1) the binary tree must be complete except to the rightmost leaves. 2) The value of the key for each node must be equal to or higher than that of the children. A heap could be presented in an array with n elements starting at the index 1 in top-down left-right order. The bottom-up heap construction algorithm provides the necessary steps to set up a binary tree, then heapifies its nodes to construct a heap. Heapify is also used to insert a key into a Heap structure to initiate a key exchange with the parent node as needed. The heapsort could be accomplished by constructing a max heap and then deleting the max number key repeatedly. The result will be the sorted keys.

The final section of this module discusses the implementation of hashing as a method to distribute keys in the hashing table. The hashing function h(K) = K mod m; denotes keys starting from 0 to m-1 (the range of the division remainder). Assigning key values to the same cell of the hash table results in collision. We reviewed two techniques to avoid collision: Separate Chaining and Linear Probing.