CST-370 Week 6

     This week, I learned about two different types of balanced trees and their associated algorithms: AVL Tree and 2-3 Tree. I also learned how to use the Heap data structure to efficiently find maximum and minimum values. Heap can be represented by the bottom-up algorithm. Finally, I learned to use Hashing for storing values in a dictionary/array to perform efficient search operations.

AVL Trees

Problem: Unbalanced trees result in operations that take O(n) time.

AVL Tree: A balanced binary search tree. The difference between the heights on the left and right subtrees is either -1, 0, or 1. (balance factor = height of left subtree - height of right subtree)

Ex: Since each node has a balance factor of -1, 0, or 1, it is an AVL tree.


AVL Tree Rotations

Rotation: A local transformation of a subtree whose balance factor has become either +2 or -2.

Four types of rotations: R(right)-rotation, L(left)-rotation, LR-rotation, RL- rotation

Ex:


    A
     \
      B
       \
        C
For performing a left rotation:

    1. B, the right child of A, moves up.
    2. A moves down to become B's left child.
    3. Any left subtree previously belonging to B becomes the right subtree of A.
      B
     / \
    A   C


        C
       /
      B
     /
    A
For performing a right rotation:
    1. B, the left child of C, moves up.
    2. C moves down and becomes B's right child.

2-3 Tree

A 2-3 tree is a search tree.

    - Each node can have one or two values (2 children's nodes or 3-children's nodes)

    - Height balanced: All leaves are at the same level.

    - If there is a node with more than 2 values, promote the middle child, creating a new level.


Heap

Complete Binary Tree: A binary tree in which every level, except possibility the last, is completely filled, and all nodes in the last level are as far left as possible.

Heap: A binary tree with the following two conditions.

    1. It should be a complete binary tree.

    2. Max heap: The number of each node is >= to the number of its children.

    or

    Min heap: The number of each node is <= to the numbers of its children.

Ex for max heap:


Using Max Heap to find the maximum value, the root value will always be the maximum value. Found in O(1)

Max Heap Operations

Insert example:

Time complexity for inserting: O(logn)

Remove max from heap:

    1. Replace root with the last leaf

    2. Heapify down (swapping with the larger child if the parent is smaller.


Heapsort - Basic idea

    - Construct a max heap with a given list of n numbers

    - Apply the delete operation of max numbers (n - 1) times.

    -> The order of deleted numbers will be the sequence of numbers in sorted order

Overall time complexity: O(nlogn)


Heap Representation and Construction

Using an array (size of n+1) to represent a heap with n nodes:

    - Store the heap in the array from index 1 to n.

    - The root node is assigned index 1 of the array. All the following nodes are stored from index 2 to n

Parental nodes are in the first [n/2] positions of the array and leaf keys occupy the last [n/2] positions (nodes with no children). Children of a key in the position i are in positions (2*i) and (2*i+1). Parent of a key in position i will be in position [i/2]


Heap construction with n random input numbers:

Top-down heap construction: Add n numbers one by one


Hashing

Worst case for chaining: O(n)

Average: O(1)

Load Factor

n = number of keys, m = size of hash table.

Load factor = n/m

Load factor too high? May result in too many collisions and less efficiency in searching for a key.

Load factor too low? May not be an efficient use of space.

    - Load factor increases as more elements/keys are added to a hash table.

Objective for rehashing:

    - Reduce the load factor to be within a pre-defined load factor. i.e. if load factor exceeds this pre-defined load factor, trigger rehashing.

Rehashing: Increase the hash table's size to be the first prime number greater than twice the previous table size.





Comments

Post a Comment

Popular posts from this blog

Week 4

Part 1 Educational Goals. My main educational goal is to achieve my bachelor's degree in computer science in 2 years. Another educational goal of mine is to do well in my upper division classes so I can be prepared for a career in software development. I would also like to strengthen my collaboration skills through the use of group projects.  Part 2 Career Goals. One of my main career goals is to become a professional software developer after graduation. I hope to leverage my current internship as an Android developer to find a new internship next summer, so I can explore different fields in software development. Part 3 Guess ETS percentile. If I had to guess, I think I would be in the 70th percentile. I feel pretty comfortable with programming, but I think I would struggle more with the theory-based questions and would have to review my notes from discrete/data structures beforehand.  Part 4 Learning Journal.  Writing material:  For my Ethics essay, I will need to c...
Read more

Week 9

 Codingbat questions Did you plan it out or throw code at it?  I gave it a few seconds of thought before throwing code at it What worked? Java methods were pretty easy to understand coming from C++ and Kotlin. What DID NOT work? Some of the methods involving indexes through me off sometimes, as it is easier to visualize by writing down your steps to the solution than it is trying to do it in your head. (same with some of the problems involving edge cases) How many tries did it take?  Most only took 1-3 tries.
Read more

CST-363 Week 1

  Relational database tables and spreadsheets look similar with both having rows and columns.  What are some important differences between the two? One of the biggest differences is that relational databases can be restored on failures. Relational databases also use SQL to retrieve and insert data. Installing and configuration a database and learning how to use it is more complicated that just reading and writing data to a file.  What are some important reasons that makes a database a useful investment of time?  Databases force data integrity and ensure it is consistent across programs. Databases can also restrict data to a program based on security rules. Databases can reduce redundancy and inconsistency.  What do you want to learn in this course that you think will be useful in your future career?  I think I would like to learn how to translate English into valid SQL queries/maybe accessing databases asynchronously as practically every company will have a...
Read more