Trees

Binary Tree

Tree Traversal

Binary Search Tree

AVL Tree

B-Tree

Balanced Search Tree

Simulator

By David Galles

B-Tree Simulator

Idea

A searching data structure like Binary Search Tree (BST) but can hold more data inside each node

=> Reduce searching time

Core Mechanism: Maximum degree A positive integer M that indicates:

1. Minimum number of children (except root): M/2
2. Maximum number of children (including root): M
3. Minimum number of elements inside one node: (M/2) - 1
4. Maximum number of elements inside one node: M - 1

The minimum number will cause merging
The maximum number will cause splitting

Operations

Revolves around merging splitting nodes.

Insertion: Insert new node at the right leaf, splits current nodes into siblings if there are more elements bounded by the maximum degree.

Recursively check parent nodes if splitting causes them to have more children than the maximum, splitting if necessary.

B+ Tree

Simulator

By David Galles

B+ Tree Simulator

Idea

B+ Tree is a B-Tree with some extra features

1. All data are stored on the leaf level
2. Leaf nodes are connected to each other like a linked list