FINAL REVIEW Data Structures Binus

FINAL REVIEW Data Structures

 Nama   : Albertius Christopher Nathan
NIM     : 2301883643
Kelas    : CB-01 / LN-01
Dosen   : Gradiyanto Sanjaya (D5327), NICKY HENDRIK SEN (NH191), WAHYU (WU191) [LN-01]
             Henry Chong (D4460), Ferdinand Ariandy Luwinda (D4522) [CB-01]
1. Linked Listsa
Linked List is pretty similar to array, but Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous location; the elements are linked using pointers.
Image result for difference between array and linked list


Linked List are divided into 2 types, the Single Linked List and Double Linked List. To read more about linked lists, you can go here 

2. Hashing, Hash Tables, and Binary Tree
Hashing is an important Data Structure which is designed to use a special function called the Hash function which is used to map a given value with a particular key for faster access of elements. The efficiency of mapping depends of the efficiency of the hash function used.

Hash Table is a data structure which stores data in an associative manner. In hash table, the data is stored in an array format where each data value has its own unique index value. Access of data becomes very fast, if we know the index of the desired data.

A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right child.
Binary tree also known as B-tree.

To read more about Hashing, Hash Tables and Binary Tree, you can go here

3. Binary Search Tree
Binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers.

  • It is called a binary tree because each tree node has maximum of two children.
  • It is called a search tree because it can be used to search for the presence of a number in O(log(n)) time
To read more about  BST, you can read here

4. AVL Tree
An AVL tree is a subtype of binary search tree. Named after it's inventors Adelson, Velskii and Landis, AVL trees have the property of dynamic self-balancing in addition to all the properties exhibited by binary search trees.

A BST is a data structure composed of nodes. It has the following guarantees:
    a. Each tree has a root node (at the top).
    b. The root node has zero, one or two child nodes.
    c. Each child node has zero, one or two child nodes, and so on.
    d. Each node has up to two children.
    e. For each node, its left descendants are less than the current node, which is less than the right descendants.

    AVL trees have an additional guarantee:
    a. The difference between the depth of right and left subtrees cannot be more than one. In order to  maintain this guarantee, an implementation of an AVL will include an algorithm to rebalance the tree when adding an additional element would upset this guarantee.

    To read more about AVL, you can go here

    5. Heap and Tries
    A heap is a tree-based data structure in which all the nodes of the tree are in a specific order.

    For example, if X is the parent node of Y, then the value of X follows a specific order with respect to the value of Y and the same order will be followed across the tree.
    The maximum number of children of a node in a heap depends on the type of heap. However, in the more commonly-used heap type, there are at most 2 children of a node and it's known as a binary heap.

     Trie is an efficient information reTrieval data structure. Using Trie, search complexities can be brought to optimal limit (key length). If we store keys in binary search tree, a well balanced BST will need time proportional to M * log N, where M is maximum string length and N is number of keys in tree. Using Trie, we can search the key in O(M) time. However the penalty is on Trie storage requirements

     To read more about Heap and Tries, you can go here

    Komentar

    Posting Komentar

    Postingan populer dari blog ini

    Heap and Tries

    Gambar
    What is HEAP? A heap is a tree-based data structure in which all the nodes of the tree are in a specific order. For example, if  X  is the parent node of  Y , then the value of  X  follows a specific order with respect to the value of  Y  and the same order will be followed across the tree. The maximum number of children of a node in a heap depends on the type of heap. However, in the more commonly-used heap type, there are at most  2  children of a node and it's known as a binary heap. In a binary heap, if the heap is a complete binary tree with  N  nodes, then it has the smallest possible height which is  l o g 2 N . Illustration of Heap In the diagram above, you can observe a particular sequence, i.e each node has greater value than any of its children. Suppose there are  N  Jobs in a queue to be done, and each job has its own priority. The job with maximum priority will get completed first than others. At each instant, we are completing a job with maxi
    Baca selengkapnya

    AVL Tree

    Gambar
    What is an AVL Tree? An AVL tree is a subtype of binary search tree. Named after it's inventors Adelson, Velskii and Landis, AVL trees have the property of dynamic self-balancing in addition to all the properties exhibited by binary search trees. A BST is a data structure composed of nodes. It has the following guarantees: Each tree has a root node (at the top). The root node has zero, one or two child nodes. Each child node has zero, one or two child nodes, and so on. Each node has up to two children. For each node, its left descendants are less than the current node, which is less than the right descendants. AVL trees have an additional guarantee: The difference between the depth of right and left subtrees cannot be more than one. In order to maintain this guarantee, an implementation of an AVL will include an algorithm to rebalance the tree when adding an additional element would upset this guarantee. AVL trees have a worst case lookup, insert and delete time of O(log
    Baca selengkapnya
    Gambar
    Single Linked List First of all, what is Linked List? Linked List is pretty similar to array, but Linked List is  a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous location; the elements are linked using pointers. ///Then, what is special about Linked Lists? Are they are just similar to Array?/// Even though array and linked lists are pretty similar, but there is some differences between arrays and linked lists. Here is the difference between array and linked list. What is Single Linked List? Single Linked List is a type of Linked Lists that only have a single pointer variable that points to the next element that will leads to the tail of Linked List, and the tail will points NULL.  here is the illustration of Single Linked List : P. S. : Head is the first element of Linked List and Tail is the last element of Linked List example of ' struct ' code : struct Scholar{       char name[25];  
    Baca selengkapnya