What is a Tree? Forest?

Data Structure & Alogirthm
2

Tree: a graph are connected and acyclic

  • Trees \iff minimally connected graph aka remove any edge will cause disconnect

  • Trees \iff maximally acyclic graph aka add any edge will cause cycle

  • \forall u,v\in V, u\ne v \implies unique path fromu tov

  • Free tree is used for an undirected connected acyclic graph without a specific vertex designated as the root.

  • Rooted tree with one vertex is designated as the root.

A forest is a collection of (0+) disjoint trees

  • A tree is also a forest.

  • Total vertices - Total Edges = # trees

More Tree

Binary Tree

Binary Search Tree

AVL Tree

Binary Index Tree (or Fenwick Tree)

Segement Tree

Quar Tree

Minimum Spanning Tree