005 - AVL Tree

AVL TREE

AVL Tree is a Binary Search Tree which can balance itself  in order to avoid the worst case scenario of a BST. To balance the tree, we need to check the tree for their balance factor every time a data is inserted into the tree. Balance factor is found by simply subtracting the left child of a node with the right child of the node. In order to achieve balance, every balance factor in a tree must be made into either -1, 0, or 1. If a balance factor doesn't satisfy the condition, the middle-most child of all the children from the unbalanced node will be "dragged" onto the unbalanced node to create a balance, replacing it's parent node.

It will look a little something like this:

This is what a left unbalanced tree looks like. Like its name, it's a tree where an unbalance happens on the left side of the tree. A rotation from the left to the right is made to balance this problem. By making the middle (median) node from the unbalanced tree into a new root for the tree, it solves the unbalances as all the balance factors in the tree satisfies the condition of an AVL tree.

This is a right unbalanced tree. It's quite literally the same thing as the left unbalanced tree with the difference of it being unbalanced on the right side of the tree. Like the previous one, we also "rotate" the tree here to the left in order to balance the tree.

004 - Review

Review

Linked List and Double Linked List

Linked List:

Linked list is a method to store information dynamically and also efficiently. It's dynamic because of the fact that we don't reserve a spot in our memory to store our data, but instead reserve a new spot whenever we want to store an information. The reason we would use this structure instead of a static one like an array list, is because it's simply more efficient to reserve a new spot in the memory when adding a new data rather than reserving spots that might not suffice or use more memory than needed.

Visualization:

source: https://www.geeksforgeeks.org/data-structures/linked-list/

Double Linked List:

Double linked list has the same concept as the normal linked list. It's called a double linked list due to the fact that instead of storing a single "next" value in a node, we store a "next" value and a "prev"(previous) value in a every single node.

"prev" holds the address of the previous node. This allows the list to be searched through in 2 different directions instead of a single one like the normal linked list.

visualization:

source: https://www.geeksforgeeks.org/doubly-linked-list/

Stack and Queue

Stack

Stack is the concept of "what you put in last get put out first". This concept can be put metaphorically as a stack of dishes or a tennis ball cylinder. It's not possible to take something out if there is something else above it in the stack. 

visualization:

source: https://www.geeksforgeeks.org/stack-data-structure-introduction-program/

Queue

The concept is actually really similar to the concept of stack. The name "queue" can be taken quite literally since that is basically what it is, a queue. In a queue, the first person that gets in a queue, gets out on the end of the queue first. This is the concept of "What you put in first, get put out first".

visualization:

source : https://www.geeksforgeeks.org/queue-data-structure/

The rear is the input direction of the queue and holds the last data in the queue. The head, on the other hand, holds the first data that was inputted and is the output direction of the queue.

Hashing and Binary Tree

Hashing

Hashing is basically giving alias that is determined by a hash function to a data. The reason that whenever we are logging in into an account, it didn’t take a long time for our account data to be retrieved is because they didn’t look and search for our account one by one. By using a hash function and turning our login information into a key, the data that is stored within the index of the key can be immediately called accurately.

Here is a diagram that I’ve made to visualize hashing:

Binary Tree
Binary Tree is a tree data structure that has the special condition of having 2 children at most, thus the word “binary” in the name. Classifying a tree as a binary tree is not that difficult since the condition of “having 2 children at most” is literally the only condition of it. This means that a binary tree’s node doesn’t have to have 2 children beneath it. As long as the number of children in a single node is less than two, it is a binary tree.

Some terminologies and types of Binary Tree might be:

-         Balanced Binary Tree:

The concept of minimizing the levels in a binary tree or in other words, “Balancing” a binary tree. Since there are operations in binary tree that depends on the height of a tree, the longer a tree is, the longer that operation will take. Thus, minimizing a tree and keep it as dense (Balanced) as possible is an important aspect.

-         Complete Binary Tree:

A binary tree will be called a completed one, if it satisfies 2 requirements: There are no missing nodes (only has 1 child), and the nodes are filled mostly on the left side of the tree rather than the right. However, it’s allowed for the last level of the tree to not be filled completely.

-         Perfect Binary Tree:

It’s a binary tree which satisfies the fact that every child is filled. that means that it will always use the maximum number of nodes available in every level.

Most of these Information used are based on:
https://www.youtube.com/watch?v=H5JubkIy_p8&t=78s

002 - Stack and Queue

Stack

Stack is the concept of "what you put in last get put out first". This concept can be put metaphorically as a stack of dishes or a tennis ball cylinder. It's not possible to take something out if there is something else above it in the stack. 

visualization: 

source: https://www.geeksforgeeks.org/stack-data-structure-introduction-program/

Operations: 

- push (insertion) : adding something on top of the stack.

- pop (deletion)   : taking something from the top of the stack.

Queue

The concept is actually really similar to the concept of stack. The name "queue" can be taken quite literally since that is basically what it is, a queue. In a queue, the first person that gets in a queue, gets out on the end of the queue first. This is the concept of "What you put in first, get put out first".

visualization:

source : https://www.geeksforgeeks.org/queue-data-structure/

It should be pretty obvious by now that the difference between queue and stack is their input and output direction. The rear is the input direction of the queue and holds the last data in the queue. The head, on the other hand, holds the first data that was inputted and is the output direction of the queue.

Operations:

- Enqueue (insertion) : add a new data to the queue. This happens on the rear of the queue.

- Dequeue (deletion) : take out the first data that was inputted in. This happens on the front of the queue.

001 - Linked List and Doubly Linked List

Linked List

Linked list is a method to store information dynamically and also efficiently. It's dynamic because of the fact that we don't reserve a spot in our memory to store our data, but instead reserve a new spot whenever we want to store an information. The reason we would use this structure instead of a static one like an array list, is because it's simply more efficient to reserve a new spot in the memory when adding a new data rather than reserving spots that might not suffice or use more memory than needed.

Visualization:

source: https://www.geeksforgeeks.org/data-structures/linked-list/

How it works:

A head stores the address of the first node in the list. In the pointed address, there is something that we call a node which consists of the data that is going to be stored first and a "next" value. A "next" holds the address of the next data that is going to be stored in the list. This would mean that every node stores an address to the next node that is added into the list. This would then create a line as shown in the image above with each node pointing at the next node in the list.

This is why we need a head to store the address of the first node. Because of that, we can search through the list from the head and go to the next value of each node to get to the end of the linked list.

When deleting a node, all we have to do is direct the previous node from the one we're trying to delete to point at the next node after it. However, do keep in mind to free the memory after the next value has been adjusted to clear the memory that was used to store the deleted node. Another thing to remember is to change the address value stored in the head to the next node after the first node when deleting a head so that the start of the linked list is not lost.

Double Linked List

Double linked list has the same concept as the normal linked list. It's called a double linked list due to the fact that instead of storing a single "next" value in a node, we store a "next" value and a "prev"(previous) value in a every single node.

"prev" holds the address of the previous node. This allows the list to be searched through in 2 different directions instead of a single one like the normal linked list.

visualization:

source: https://www.geeksforgeeks.org/doubly-linked-list/

Double linked list have a head and a tail. Tail holds the address of the last node in the linked list. This makes it possible to know do an operation from the back of the linked list instead of being forced to always start from the head like the normal linked list.

P.S:

Operations work similarly with normal linked list. However, always keep in mind to also adjust the value of "prev" when doing operations.

003 - Hashing and Binary Tree

Hashing

Hashing is basically giving alias that is determined by a hash function to a data. The reason that whenever we are logging in into an account, it didn’t take a long time for our account data to be retrieved is because they didn’t look and search for our account one by one. By using a hash function and turning our login information into a key, the data that is stored within the index of the key can be immediately called accurately.

Here is a diagram that I’ve made to visualize hashing:

This is the reason that, whenever someone is signing up for an account, having the same username as someone else is not a possibility. It’s because those names are used as keys to the specific address in the database. Simply speak, your username is equivalent to the address of your data.

Binary Tree

Binary Tree is a tree data structure that has the special condition of having 2 children at most, thus the word “binary” in the name. Classifying a tree as a binary tree is not that difficult since the condition of “having 2 children at most” is literally the only condition of it. This means that a binary tree’s node doesn’t have to have 2 children beneath it. As long as the number of children in a single node is less than two, it is a binary tree.

Nodes that don’t have a child (the leaf of the tree) or missing a child (either left or right child) has the value of the missing child set as NULL. This basically means that all of the missing child’s node exist but they have NULL values inside of them.

Some terminologies and types of Binary Tree might be:

-         Balanced Binary Tree:

The concept of minimizing the levels in a binary tree or in other words, “Balancing” a binary tree. Since there are operations in binary tree that depends on the height of a tree, the longer a tree is, the longer that operation will take. Thus, minimizing a tree and keep it as dense (Balanced) as possible is an important aspect.

-         Complete Binary Tree:

A binary tree will be called a completed one, if it satisfies 2 requirements: There are no missing nodes (only has 1 child), and the nodes are filled mostly on the left side of the tree rather than the right. However, it’s allowed for the last level of the tree to not be filled completely.

-         Perfect Binary Tree:

It’s a binary tree which satisfies the fact that every child is filled. that means that it will always use the maximum number of nodes available in every level.

Most of the Information used are based on:
https://www.youtube.com/watch?v=H5JubkIy_p8&t=78s

A highly recommended channel to learn Data Structure.