Trees
Last updated
Last updated
A Tree data structure is a hierarchical way to organize data, with a topmost node called the root and connected nodes called children. Each node can have multiple children, forming a recursive structure.
There are several types of tree data structures, each with its own unique properties and use cases:
Binary Tree: A tree data structure in which each node has at most two children, typically referred to as the left child and the right child.
Ternary Tree: A tree data structure where each node has at most three children, usually distinguished as left, mid, and right.
N-ary Tree (Generic Tree): A tree data structure where each node can have n number of children.
Binary Search Tree: A binary tree in which for each node, the values of all the nodes in its left subtree are lesser or equal and the values of all nodes in right subtree are greater.
AVL Tree: A self-balancing binary search tree where the difference between heights of left and right subtrees cannot be more than one for all nodes.
Red-Black Tree: A kind of self-balancing binary search tree where each node contains an extra bit for denoting the color of the node, either red or black.
B-Tree: A self-balancing search tree, mainly used in databases and file systems, where a node can have more than two children.
Heap: It is a special tree-based data structure where the tree is a complete binary tree. It satisfies the heap property, which states that the key of each node is always greater than or equal to (in a Max Heap) or less than or equal to (in a Min Heap) the keys of its children.
Binary Heap: It is a complete binary tree used to efficiently store data and retrieve the max or min element. It obeys the property that the root of any subtree has a higher (or lower, based on the type of heap) value than all the nodes in its subtree. It comes in two forms: Min Heap and Max Heap. In a Min Heap, the key at the root must be minimum among all keys present in the Binary Heap, and in a Max Heap, the key at the root must be maximum. A binary heap is a complete binary tree. All levels of the tree, except possibly the last one (deepest) are fully filled. Binary Heaps are used in various applications like implementing priority queues, in operating systems for prioritizing processes, in networking for prioritizing packets for timely delivery, in databases for indexing data, and in pathfinding algorithms.
Trie: A Trie, also known as a prefix tree, is a tree-based data structure used for efficiently storing and retrieving strings. It is particularly useful for tasks like autocomplete or searching for words with a given prefix.
There are some operations of the Trees in the data structure:
Traversal: Visit each node in the tree in a specific order. Common traversal methods include Preorder, Inorder, and Postorder.
Insertion: Insert a new node into the tree.
Deletion: Delete a node into the tree.
Search: Search for a specific node in the tree.
Update: Update a node into the tree.
Sort: This operation arranges elements in a specific order.
Height of Tree: Calculate the height or depth of the tree.
Level of a Node: Determine the level of a given node.
Find Parent: Find the parent of a given node.
Find Children: Find the children of a given node.
Find Siblings: Find the siblings of a given node.
Find all Leaf Nodes: Find all nodes in the tree that have no children.
| Tree | Access | Search | Insertion | Deletion |
|---|---|---|---|---|
Simple Tree
O(N)
O(N)
O(N)
O(N)
Ternary Search Tree
N/A
O(H)
O(H)
O(H)
Binary Tree
O(N)
O(N)
O(N)
O(N)
Binary Search Tree
O(N)
O(N)
O(N)
O(N)
AVL Tree
O(log N)
O(log N)
O(log N)
O(log N)
Red-Black Tree
O(log N)
O(log N)
O(log N)
O(log N)
B-Tree
O(log N)
O(log N)
O(log N)
O(log N)
Heap
O(1)
O(N)
O(log N)
O(log N)
Trie
N/A
O(L)
O(L)
O(L)