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.