Learning Journal

 This week we learn about AVL tree.One problem with binary search tress is that if the tree is too unbalanced or skewed, the operation can be linear time. The AVL tree is a balanced binary search tree, and the difference in height between left and right subtrees is either -1, 0 or 1. The difference is called the balance factor which is height of the either the left subtree and the height of the right subtree. AVL tree uses rotation as its operations. A rotation is a local transformation of a subtree whose balance factor has become either +2 or -2. In other words after inserting a new node, if the AVL tree becomes unbalanced, rotations are applied to restore balance. The four rotations are Right rotation, Left rotation, LR rotation and RL rotation. Another topic that was discuss is 2-3 trees. A 2-3 tree is a search tree where each node can have oen or two values (2-node or 3-nodes) All leaves are at the same level.  We also discuss about Heap and Heapsort. A complete binary tre...

For week 3 of CST370 Design and Analysis of Algorithms we learn about quick sort. Quick sort was first proposed by C.A.R Hoare in 1962. It uses Divide-and-Conquer and very popular but its efficiency can be tricky. Basically quicksort an n-element array it "Divides", in partition, the array into two subarrays around a pivot such that elements in the lower subarray elements in upper subarray. It then concquer recursively sort the two subarrays and combine. Quicksort worst case scenario when the data is already sorted and its has O(n^2) at its worst. Best case however it has O(nlogn) and its average case and use has that efficiency.  We also learn this week about Binary tree traversals. A binary tree is a divide and conquer ready data structure. One classic problem with binary trees is to systematically visit each node. There are three binary tree traversals called inorder, preoder and postorder. Preorder, from the word "Pre", traversal visites the node in the order Ro...