Posts

AVL Tree & B-Tree

Image
AVL Tree What is AVL Tree? AVL Tree is a self-balancing Binary Search Tree (BST), link to learn about BST  where the difference between the depth of left and right sub-trees cannot be more than one for all nodes. To get the balance factor we get the longest depth of each left  and right of the node. Then using this formula to get the balance, balance = depth of left - depth of right. This is an example of a balanced tree: This is an example of a unbalanced tree: As shown, there are 2 node that violates the balance because there are nodes with balance more than one. If this happens we will choose the deepest node that violates the balance factor to be fixed. Why AVL Trees? Most of the BST operations take O(h) time where h is the height of BST. Worst cast senario may become O(n) for a skewed Binary tree . If we make sure that height of the tree remains O(log n) after every insertion or deletion, then we can guarantee an upper bound of O(log n) for all BST op...
1 comment
Read more

Mid - Sem 2 - Summary

Linked List Linked List is a linear data structure, list of elements are stored randomly at a contagious memory location. Which the elements are accessible using pointers. Unlike array, data's are stored linearly or side by side in a memory and size of memory are limited. A Linked List consist of node, we can insert data inside the node. The node also consist of a 'next' pointer which will point to the next node in the linked list. This next pointer are what connects the linked list together. We also have 'head' this is to mark the beginning or the first node. we can also use 'tail' to mark the last node. The last node will not point anything or pointer a 'NULL'. There are 2 ways of linked list, namely, single linked list and doubly linked list. In doubly linked list, the only different is that, they have a 'prev' pointer. This pointer is use to point the previous node in the linked list. A linked list has a couple important functi...
Post a Comment
Read more

Hash Tables and Binary Tree

Image
Hashing and Hash Tables Hashing Hashing is the transformation of a string of characters into a shorter length value or key that represents the original string. Hashing is used to index and retrieve items in a database because it is faster to find item using the shorter hashed key than to find it using the original value. such function is called hash function which come with different forms and each will gives different result. for example you have a input of integers such as "11", "12", "13", "14" and we place them in an array. List = [11, 12, 13, 14] If we want to find the number "14" it will take time complexity of O(n). What if we have a huge amount of data stored, it will be to long to find a specific number. but with hashing and hash table with will only took time complexity of O(1).  Let the hash function H(x) maps the value X at the index in x%10 in an array. It will be shown: The same happen if the ...
Post a Comment
Read more