-
Notifications
You must be signed in to change notification settings - Fork 0
DS: Trees
Rishav Ray edited this page May 14, 2025
·
2 revisions
-
A graph is a collection of nodes (or vertices) connected by edges (or links), representing relationships between data elements. A tree is a special type of graph where there are no cycles.
-
There are fourteen types of trees: Full Binary Trees, Degenerate Binary Trees, Skewed Binary Trees, Complete Binary Trees, Perfect Binary Trees, Balanced Binary Trees, Binary Search Trees, Heap Trees, Segment Trees, AVL Trees, Red Black Trees, B-Trees, & Tries.
-
In a tree, the top most node has no parents and is called the root-node, and nodes that have no children are called leaf-nodes.
-
The height of a tree is measured as the number of edges from the root to the furthest down leaf.
-
A binary trees are trees where each node has at most 2 children.
- Full binary trees are binary trees where each node has 0 or 2 children.
- Degenerate binary trees are binary trees where each internal node has only one child.
- Skewed binary trees are binary trees that are dominated either by the left nodes or the right nodes.
- Complete binary trees are binary trees where all levels are completely filled except possibly the last level and the last level has all keys as left as possible.
- Perfect binary trees are binary trees where each level is full.
- Balanced binary trees are binary trees whose left and right subtrees' heights differ by not more than 1.
- Binary search tree are binary trees used for efficient searches/insertions/deletions of sorted data. In these trees, each node's value is greater than that of its entire left subtree and is less than that of its entire right subtree.
- Heap trees are binary trees where the value of each node is either greater than or equal to (max-heap) or less than or equal to (min-heap) the values of its children.
- Segment trees are binary trees that store information on intervals of fixed-size arrays.
- AVL Trees are self-balancing binary search trees, where the difference between heights of left and right subtrees of each node doesn't exceed 1.
- Red-black trees are self-balanced binary search trees where each node has an extra bit, denoting either red or black. Although the balance of the tree is not perfect, it is significant.
- B-trees are self-balancing trees that allow efficient search, insertion, and deletion of data items. A B-tree is characterized by a fixed maximum degree (or order), which determines the maximum number of child nodes that a parent node can have. Each node in a B-tree can have multiple child nodes and multiple keys, and the keys are used to index and locate data items. These aren't used for range queries, unlike B+ trees.
- B+ trees are B-trees but with a major difference: each internal node contains keys for indexing and locating data-items and each leaf-nodes contains the actual data-items. B+ trees are essentially linked lists of leaf nodes (where all actual data is stored), with a hierarchy of index nodes above them to route searches efficiently.
- Tries, also known as prefix trees, are trees used for storing a dynamic set of strings, and is especially efficient for strings where there is a lot of overlap in prefixes.