Problems on Binary Tree Understand everything about Binary Search Tree Binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers in a tree data structure. It can be used to search for the presence of a number in O(log(n)) time and a simple traversal gives the numbers in sorted order.
Data Structures Fibonacci Heap A Fibonacci heap is a heap data structure similar to the binomial heap. It uses Fibonacci numbers and also used to implement the priority queue element in Dijkstra’s shortest path algorithm which reduces the time complexity from O(m log n) to O(m + n log n)
Problems on Binary Tree Binary Tree A binary tree is a tree data structure in which each node has upto two children (that is a maximum of two children nodes), which are referred to as the left child and the right child. Implementation and applications of binary tree
Data Structures Max Heap and Min Heap A min heap is a heap where every single parent node, including the root, is less than or equal to the value of its children nodes. The most important property of a min heap is that the node with the smallest, or minimum value, will always be the root node. Max heap is similar
Data Structures K Dimensional Tree / (K D Tree) K Dimensional tree (or k-d tree) is a tree data structure that is used to represent points in a k-dimensional space. It is used for various applications like nearest point (in k-dimensional space), efficient storage of spatial data, range search. We implemented it in C++ and explained the operations
Data Structures Octree data structure Octree is a tree data structure where each internal node has 8 children. An octree is generally used to represent relation between objects in a 3-dimensional space. It is used in 3D computer graphics. Octrees are also used for nearest neighbor search which can be done easily in logarithmic time.
Data Structures Palindromic Tree (Eertree) Palindromic tree (Eertree) is a tree based data structure that is specifically used to tackle problems involving palindromes of a string like 'longest palindrome in a string', 'count of plaindromic substrings'. It keeps track of all palindromic substrings of a string in linear time and space
Data Structures Fusion Tree Fusion tree is a tree data structure that implements associative array in a known universe size. Fusion trees are used to solve predecessor and successor problem. We have covered sketch, parallel comparison, predecessor and successor and insert operations in O(log N) time and O(N) space complexity
Data Structures Quadtree Quadtree is a tree data structure which is used to represent 2-dimensional space. It finds major applications in computer graphics where it is used to represent relations between objects in a 2D space and for image compression. We discussed point region (PR) quadtree which store points in a 2D space
Data Structures Y fast trie Y-fast trie is a data structure used to store integers from a bounded domain. It has two data structures X fast trie and balanced binary search tree with the change being we operate on representative values r in X-fast tries, and the leaf nodes point to balanced binary search trees instead of values
Data Structures X-fast trie X-fast trie is a data structure used to store integers from a bounded domain. It is a bitwise trie, i.e. a binary tree where each subtree stores values having binary representations with common prefix. It is a trie of hash tables and supports successor and predecessor operations in log log U time
Data Structures Treap / Randomized cartesian tree A treap is a height balanced binary tree with heap properties. It is used to store a sequence in a tree, which allows for various applications like searching. It takes O(log N) time complexity for search, insert and delete operations and takes O(N) space complexity
Data Structures Cartesian Tree A Cartesian tree is a binary rooted tree data structure that can answer range queries can be answered by finding least common ancestors in the tree. An inorder traversal of the tree would give the original sequence used to form the tree. It is used as binary search tree for an ordered sequence
Data Structures 2D Fenwick Tree / 2D Binary Indexed Tree Fenwick Tree is used to answer range or interval queries in an array in logarithmic time. Fenwick tree can be generalized to multiple dimensions. 2D Fenwick tree is one such implementation used to answer sub-matrix queries, i.e. queries in 2 dimensions. It requires the operation to be invertible.
Data Structures 2D Segment Tree Segment Tree is used to answer range queries in an array. The data structure can be extended to 2 dimensions to answer sub-matrix queries in logarithmic time. Some examples of these queries are Maximum element in sub-matrix It can be seen as a segment tree of segment trees. We give an example for it
Data Structures Fenwick Tree (Binary Indexed Tree) Fenwick Tree / Binary indexed tree (BIT) is a data structure used to process interval/range based queries. Compared to segment tree data structure, Fenwick tree uses less space and is simpler to implement. One disadvantage is that it can be only used with an operation that is invertible.
Data Structures Segment Tree A segment tree is a divide and conquer based data structure used to store information about intervals of some linear data structure. It is a height-balanced binary tree where every node corresponds to an interval of the array. It allows processing interval or range queries in logarithmic time
Data Structures Trie data structure A trie (digital tree, radix tree, prefix tree) is a kind of an ordered search tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. Worst case search time complexity is Θ(key_length) and trie is widely used in real life applications
Data Structures B-Tree Deletion A B-tree is a tree data structure that keeps data sorted and allows searches, insertions, and deletions in logarithmic amortized time. Deletion in a B Tree is similar to insertion. At first the node from which a value is to be deleted is searched. If found out, then the value is deleted.
Data Structures Ternary Search Trees Ternary Search Tree is a special type of trie data structure and is widely used as an low memory alternative to trie in a vast range of applications like spell check and near neighbor searching. The average case time complexity is O(log N) for look-up, insertion and deletion operation.
git How Git uses Tree data structure concepts? We have explored how Git version control system rely on Tree data structure concepts for its internal working. We have given an overview of the various important concepts in Git such as object store, index, blobs, tree, commit, tags and others.
red black tree Red Black Tree: Deletion We will explore the deletion operation on a Red Black tree in the session. Deleting a value in Red Black tree takes O(log N) time complexity and O(N) space complexity. A red–black tree is a kind of self-balancing binary search tree in computer science.
red black tree Red Black Tree: Insertion We will explore the insertion operation on a Red Black tree in the session. Inserting a value in Red Black tree takes O(log N) time complexity and O(N) space complexity. A red–black tree is a kind of self-balancing binary search tree in computer science.
red black tree Red Black Tree: Search We will explore the search operation on a Red Black tree in the session. Searching in Red Black tree takes O(log N) time complexity and O(N) space complexity. A red–black tree is a kind of self-balancing binary search tree in computer science.