Trees

Overview

A tree is a acyclic connected graph.

Conventional tree operations are insert, search, remove, and traverse.

Tree's usually have a designated root that indicates the top of the tree. Leaves refer to nodes with no children. A parent is the node above the current one. A child is the node below the current one.

Properties

A tree is balanced when every path from root to leaf has the same length.

Binary Search Trees

In a binary tree, each node contains one element and has at most two child nodes.A binary search tree (BST) is a binary tree with the following requirements:

  • ∀ y ∈ left subtree of x, y ≤ x
  • ∀ y ∈ right subtree of x, y ≥ x
Operation Best Complexity Worst Complexity
Insert \(O(\log n)\) \(O(n)\)
Search \(O(\log n)\) \(O(n)\)
Delete \(O(\log n)\) \(O(n)\)

A binary search tree is complete if every node has zero or two children and all leaves are at the same level.

The shape of the binary search tree depends entirely on the order of insertions and deletions, and can become degenerate. A skewed binary tree can greatly affect performance.

Self-Balancing Binary Search Trees

Examples include:

  • AVL trees
  • Red-black trees

TODO B-Tree

TODO Trie