CST 370 Week 6 Learning Journal Entry

-

Trees, Heaps, and Hashing

This week we learned about four types of data structures: AVL trees, 2-3 trees, heaps, and hashing. 

AVL Trees

AVL Trees are balanced binary search trees that have a balance factor. Balance factors are computed by taking the difference between the height of the left subtree and the height of the right subtree. An AVL tree is said to be balanced if the balance factor is -1, 0, or 1. If the tree is unbalanced, one of four rotations can be used to transform the binary search tree into a balanced tree: Left Rotation, Right Rotation, Left-Right Rotation, or Right-Left Rotation. Below is how to determine what rotation is needed: 

  • Left Rotation: The root has a negative number smaller than -1.
  • Right Rotation: The root has a positive number greater than 1. 
  • Left-Right Rotation: The root has a positive number greater than 1, and the node on the left has a negative number. In this case, we rotate the node with the negative number to the left and then rotate the root with the positive number greater than 1 to the right. 
  • Right-Left Rotation: The root has a negative number smaller than -1, and the node on the right has a positive number. In this case, we rotate the node on the right with the positive number to the right and then rotate the root with the negative number less than 1 to the left. 
Below is an example of each rotation. 


2-3 Trees

In addition to AVL trees, we also learned about 2-3 trees. 2-3 trees allow each node to have one value (2-node) or two values (3-node). If a node has two values, the left subtree has values that are less than the lesser of the two parent nodes, the right subtree has values that are greater than the greater of the two parent nodes, and the middle subtree contains values that are between the two parent nodes. When constructing a 2-3 tree, if a third value is added to a node, the middle value is promoted to be a parent node of the other two. This process is shown in the picture below: 


Heaps

Heaps are considered to be complete binary trees where two specific conditions are met:
  1. every level is filled except the last level
  2. all nodes in the last level are far left
Heaps can be classified as a max heap or a min-heap. In a max heap, the parent nodes are greater than each of the child nodes. In a min heap, the parent nodes are smaller than each of the child nodes. In these trees, there is no requirement that the lesser of the children is on the left and the greater of the children is on the right as it is in an AVL tree. An example of the two can be found below. 


Hashing

A hash table is a data structure that uses a technique called hashing to store data. This technique consists of three components: 
  1. keys (unique pieces of data)
  2. a hash function (key%num)
  3. hash table (where keys are stored)
The hash function determines where a key is stored in the hash table. For example, if I wanted to store 8 in a table of size 5, I would use the hash function (8%5 =3) to find that 8 should be stored in position 3 of the hash table. 

In addition to these components, we also need to take into consideration what to do if two keys need to be stored at the same position of the hash table. For example, we know that the key of 8 is stored at position 3 in a table of size, but so is a key of 3 since 3%5=3.  If this happens we can take two approaches to store the key of 3: 
  1. separate chaining - the key of 3 is appended to position 3 after key 8
  2. linear probing - we search the table for the next available position and store 3 in that position
Linear Probing
Separate Chaining

In addition to these processes, we also need to keep track of a load factor as we insert keys into a hash. The load factor is computed by dividing the number of keys in the hash table and the table size. We can compute the load factor and compare it to a predefined load. We can check if the load factor is greater than the predefined load factor and if it is, we can double the table size and increase it to the next prime number.  The previous keys are then entered into the new hash table and the keys can continue to be inserted. This process is called rehashing. An example of this can be found below. 












Comments

Post a Comment

Popular posts from this blog

CST 334 Week 1 Journal Entry

-
Image
Week 1: Introduction to Operating Systems One of the main topics that I learned about this week in CST 334 was operating systems and the role they play in running programs. Operation Systems have two main tasks. One of the tasks is to provide an abstraction layer to the user. This layer shields hardware information from the user, as the user should not have access to it. In addition to the layer of abstraction, the operating system also acts as a resource manager. It optimizes the use of the resources in a computer while allocating them to each program in a fair and equitable manner.  Both of these tasks are completed with the help of two modes provided by the CPU: kernel mode and user mode. While in user mode, the information about the hardware is hidden, and the user is provided an address space to do the intended job. This mode provides the user with access to user, application, and system programs. While in kernel mode, the administor has access to hardware and can change the m...
Read more

CST 311 Week 8 Journal Entry

-
Image
Operational Security and Overall Class Reflection This week, we learned about operational security. Two types of operational security methods were discussed: firewalls and intrusion detection systems. Firewalls help filter out packets passing from the Internet to an internal network. They are designed to prevent denial of service attacks and illegal modifications of internal data and only allow authorized access to a network. This can help keep the untrusted packets out of an internal network and let the trusted packets in.  There are three types of firewalls. First, there is a firewall with stateless packet filtering. This firewall decides which packet to forward or drop based on information such as IP address, TCP/UDP port numbers, ICMP message types, and TCP SYN and ACK bits. The firewall can be set so that packets with given information can be evaluated based on rules, such as ACK =0, and can be blocked from entering the internal network.  Second, there is a firewall with ...
Read more

CST 311 Week 5 Journal Entry

-
Image
Network Layer: Data Plane This week, we had an introduction to the network layer and learned about the data plane. The network layer has the responsibility of routing data from host to host via segments or packets. When sending data, segments are encapsulated into datagrams that hold the data, and the network adds header information to help with the routing process. Routers use the header information to keep the datagrams in order and determine their next hop. Receiving data is sent from the network to the transport layer and then to the appropriate application. In this process, the network is responsible for forwarding packets from one router to another until it reaches its destination and determining the route that needs to be taken to get packets from one place to its intended destination.  In the network layer, there are two planes: the data plane and the control plane. The data plane is local and functions in each router. When datagrams arrive at a router, the next port is det...
Read more