Use of Binary Trees
Use of Binary Trees
Overview
- A Binary Tree is a particular kind of graph that features hierarchical relations.
- It is a tree data structure where each node can have at most two children, typically distinguished as left child and right child.
Key Concepts
- Root: The top node in a binary tree.
- Child: A node directly connected to another node, considering the direction of edges.
- Parent: The converse notion of a child.
- Leaf: A node with no children.
- Subtree: Subset of a binary tree that includes a parent and all descendants of that parent.
Tree Traversal
- Pre-order Traversal: In this traversal method, root node is processed before its child nodes. So, Root -> Left Subtree -> Right Subtree
- In-order Traversal: In this method, root node is processed between its child nodes. So, Left Subtree -> Root -> Right Subtree
- Post-order Traversal: In this method, root node is processed after its child nodes. So, Left Subtree -> Right Subtree -> Root
Binary Search Trees (BST)
- A particular type of binary tree, it provides efficient access to ordered data and maintains order over insertions and deletions.
- All keys in the left subtree of a node are less than the node, and all keys in the right subtree are greater.
Use of Binary Trees
- They are used for searching and sorting data quickly.
- Provides efficient and organised storage of data.
- They are vital for syntax parsing in compilers.
- Used in many tree-based data structures like AVL trees and Red-Black trees.
- Applications also include path-finding algorithms used in AI and games.
Properties of Binary Trees
- Height of tree: Number of edges in the longest path from root to a leaf.
- Size of tree: Number of nodes in tree.
- Balanced Binary Tree: A binary tree where the difference of height between left and right subtrees of every node is not more than one.
Binary Heap
- A complete binary tree which is either densely packed or is as densely packed as possible, with the elements appropriately placed for a min heap or max heap.
- A max heap has the property that the parent node is greater than or equal to its child nodes.
- A min heap has the property that the parent node is less than or equal to its child nodes.
Operations on Binary Trees
- Insertion: Adding a new node.
- Deletion: Removing a node.
- Searching: Finding a node with given properties.
- Traversal: Visiting each node of tree in a specific order.
Time Complexity
- For most operations like search, insert, delete on a binary search tree take time proportional to the height of the tree.
- For a balanced binary tree with n nodes, these operations run in O(log n) time.
- If the tree is not balanced, these operations can take up to O(n) time in worst case scenario.