Posts

AVL Tree & B Tree

Image
AVL Tree AVL tree is a self-balancing binary search tree in which each node maintains an extra information called as balance factor whose value is either -1, 0 or +1. AVL tree got its name after its inventor Georgy Adelson-Velsky and Landis. Balance Factor Balance factor of a node in an AVL tree is the difference between the height of the left subtree and that of right subtree of that node. Balance Factor = (Height of Left Subtree - Height of Right Subtree) or (Height of Right Subtree - Height of Left Subtree) The self balancing property of an avl tree is maintained by the balance factor. The value of balance factor should always be -1, 0 or +1. AVL Rotations Left Rotation If a tree becomes unbalanced, when a node is inserted into the right subtree of the right subtree, then we perform a single left rotation Right Rotation AVL tree may become unbalanced, if a node is inserted in the left subtree of the left subtree. The tree then needs a right
1 comment
Read more

Data Structure Summary

Image
Linked List LinkedList  − A Linked List contains the connection link to the first link called First and to the last link called Last. Singly Linked List   A singly linked list is a set of nodes where each node has two fields ‘data’ and ‘link’. The ‘data’ field stores actual piece of information and ‘link’ field is used to point to next node. Doubly Linked List A doubly linked list  contains an extra pointer, typically called  previous pointer , together with next pointer and data which are there in singly linked list. Difference between Singly linked list and Doubly linked list In SingleLinkList, the traversal can be done using the next node link only. In DoublyLinkList, the traversal can be done using the previous node link or the next node link. The SingleLinkList occupies less memory than DoublyLinkList as it has only 2 fields. The DoublyLinkList occupies more memory than SingleLinkList as it has 3 fields. Less efficient access to elements. More efficient
1 comment
Read more

Double Linked List

Image
    Doubly Linked List is a variation of Linked list in which navigation is possible in both ways, either forward and backward easily as compared to Single Linked List. Following are the important terms to understand the concept of doubly linked list. LinkedList  − A Linked List contains the connection link to the first link called First and to the last link called Last. Link  − Each link of a linked list can store a data called an element. Next  − Each link of a linked list contains a link to the next link called Next. Prev  − Each link of a linked list contains a link to the previous link called Prev. Basic Operations Following are the basic operations supported by a list. Insertion  − Adds an element at the beginning of the list. Deletion  − Deletes an element at the beginning of the list. Insert Last  − Adds an element at the end of the list. Delete Last  − Deletes an element from the end of the list. Insert After  − Adds an element after an i
Post a Comment
Read more

Binary Tree

Image
A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller "subtrees" on either side. A null pointer represents a binary tree with no elements -- the empty tree. The formal recursive definition is: a  binary tree  is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a  binary tree .        A "binary search tree" (BST) or "ordered binary tree" is a type of binary tree where the nodes are arranged in order: for each node, all elements in its left subtree are less-or-equal to the node (<=), and all the elements in its right subtree are greater than the node (>).  Types of binary tree A  full binary tree  which is also called as
Post a Comment
Read more

Hashing Table

Image
Hashing    A hash is a function that converts an input of letters and numbers into an encrypted output of a fixed length. Key Takeaways : A hash is a function that meets the encrypted demands needed to solve for a blockchain computation. A hash, like a nonce or a solution, is the backbone of the blockchain network. Hashes are of a fixed length since it makes it nearly impossible to guess the length of the hash if someone was trying to crack the blockchain. A hash is developed based on the information present in the block header.    Hashing requires processing the data from a block through a mathematical hash function, which results in an output of a fixed length. Using a fixed-length output increases security since anyone trying to decrypt the hash won’t be able to tell how long or short the input is simply by looking at the length of the output.Solving the hash starts with the data available in the block header and is essentially solving a complex mathema
Post a Comment
Read more