Segment Tree

What is a Tree?

A Tree is a non-linear data structure and a hierarchy consisting of a collection of nodes such that each node of the tree stores a value and a list of references to other nodes (the “children”)....

Types of Trees in Data Structure based on the number of children:

Types of Trees in Data Structure based on the number of children...

1. Binary Tree

A binary Tree is defined as a Tree data structure with at most 2 children. Since each element in a binary tree can have only 2 children, we typically name them the left and right child....

2. Ternary Tree

A Ternary Tree is a tree data structure in which each node has at most three child nodes, usually distinguished as “left”, “mid” and “right”....

3. N-ary Tree (Generic Tree)

Generic trees are a collection of nodes where each node is a data structure that consists of records and a list of references to its children(duplicate references are not allowed). Unlike the linked list, each node stores the address of multiple nodes....

Special Types of Trees in Data Structure based on the nodes’ values:

1. Binary Search Tree...

1. Binary Search Tree

A binary Search Tree is a node-based binary tree data structure that has the following properties:...

2. AVL Tree

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees for any node cannot be more than one....

3. Red-Black Tree

A red-black tree is a kind of self-balancing binary search tree where each node has an extra bit, and that bit is often interpreted as the color (red or black). These colors are used to ensure that the tree remains balanced during insertions and deletions.  Although the balance of the tree is not perfect, it is good enough to reduce the searching time and maintain it around O(log n) time, where n is the total number of elements in the tree....

4. B-Tree

B-Tree is a self-balancing search tree. In most of the other self-balancing search trees (like AVL and Red-Black Trees), it is assumed that everything is in the main memory....

Properties of B-Tree:

All leaves are at the same level. B-Tree is defined by the term minimum degree ‘t‘. The value of ‘t‘ depends upon disk block size. Every node except the root must contain at least t-1 keys. The root may contain a minimum of 1 key. All nodes (including root) may contain at most (2*t – 1) keys. The number of children of a node is equal to the number of keys in it plus 1. All keys of a node are sorted in increasing order. The child between two keys k1 and k2 contains all keys in the range from k1 and k2. B-Tree grows and shrinks from the root which is unlike Binary Search Tree. Binary Search Trees grow downward and also shrink from downward. Like other balanced Binary Search Trees, the time complexity to search, insert and delete is O(log n). Insertion of a Node in B-Tree happens only at Leaf Node....

5. B+ Tree

B+ tree eliminates the drawback B-tree used for indexing by storing data pointers only at the leaf nodes of the tree. Thus, the structure of leaf nodes of a B+ tree is quite different from the structure of internal nodes of the B tree....

6. Segment Tree

In computer science, a Segment Tree, also known as a statistic tree, is a tree data structure used for storing information about intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, it’s a structure that cannot be modified once it’s built. A similar data structure is the interval tree....