Introduction to Binary Trees

[Qingquan-Li]

1. Definition of Binary Tree

• A binary tree is a tree data structure where each node has at most two children, referred to as the left child and the right child.
• It is a specialized form of a tree where every node has a maximum of two children.

2. Properties of Binary Trees

2.1 Level

The level of a node in a binary tree is the number of branches (edges) on the path from the root to the node. For example, the level of the root node of a binary tree is 0, and the level of the children of the root node is 1.

    A     (at level 0)
   / \
  B   C   (at level 1)
 / \
D   E     (at level 2)

2.2 Height

The height of a binary tree is the number of nodes on the longest path from the root to a leaf.

    A    
   / \   
  B   C  
 / \ 
D   E

The height of this binary tree is 3. Longest path: A-B-D or A-B-E

2.3 Balanced Tree

A binary tree where the heights of the two child subtrees of any node differ by no more than one.

    A    
   / \   
  B   C  
 / \ 
D   E

A binary tree is considered balanced if the height of the left and right subtrees of any node differ by no more than one. This property ensures that the tree is approximately balanced, preventing it from becoming too skewed or resembling a linear structure, like a linked list.

2.4 Complete Binary Tree

All levels are fully filled except possibly the last level, which is filled from left to right.

    A
   / \
  B   C
 / \ / 
D  E F  

2.5 Perfect Binary Tree

All internal nodes have exactly two children and all leaves are at the same level.

    A
   / \
  B   C
 / \ / \
D  E F  G

2.6 Degenerate (or Pathological) Tree

A tree where each parent node has only one child, effectively a linked list.

A
 \
  B
   \
    C

3. Types of Binary Trees

Three important types of binary trees: Binary Search Tree (BST), AVL Tree, and Red-Black Tree.

3.1 Binary Search Tree (BST)

A BST is a node-based binary tree where each node has a comparable key, and the keys in the left subtree of a node are less than the node's key, while those in the right subtree are greater.

Example BST:

    8
   / \
  3   10
 / \    \
1   6    14
   / \   /
  4   7 13

3.2 AVL Tree

An AVL tree is a self-balancing BST where the heights of the two child subtrees of any node differ by no more than one.

Example AVL Tree:

    9
   / \
  5   10
 / \
2   6

3.3 Red-Black Tree

A Red-Black Tree is a self-balancing BST where each node has an extra bit for color ("red" or "black"). This color bit ensures that the tree remains approximately balanced during insertions and deletions.

Example Red-Black Tree:

    7B
   /  \
  3R   18B
 / \   /  \
1B 5B 14R  19R
       \
       17B

In these representations:

• BST: Follows the BST property but not necessarily balanced.
• AVL Tree: Balanced with the AVL property (the balance factor of each node is -1, 0, or 1).
• Red-Black Tree: Follows the Red-Black Tree properties, including color assignments and balancing criteria.

4. Applications of Binary Trees

• Data Storage: BSTs are used for efficient searching and sorting.
• File Systems and Databases: AVL and Red-Black Trees are used in file systems and databases for quick data retrieval.
• Priority Queues: Binary Heaps are a type of binary tree used in implementing priority queues.
• Syntax Trees: Used in compilers to represent the structure of program code.
• Huffman Coding Tree: Used in data compression algorithms.