Data structures

A data structure is a way of organizing and storing data in memory. Different data structures are beneficial in different situations: some allow dynamic expansion of data, others provide faster access, and some offer features that are especially useful for specific tasks.

Set

A set is an abstract data structure used to store a collection of unordered and unique elements.

In a typical implementation, such as a hash set, each element is assigned to a bucket based on a hash function. Let the set consist of \(n\) buckets, denoted as \(b_i\), where \(i \in \{1, \ldots, n\}\). Each bucket \(b_i\) contains a subset of the elements that hash to index \(i\).

Let \(\mathbb{E}\) be the universe of elements that can potentially be stored in the set. A hash function

\[ f : \mathbb{E} \rightarrow \{1, \ldots, n\} \]

maps each element \(e \in \mathbb{E}\) to the index of the bucket it belongs to. That is, element \(e\) is stored in bucket \(b_{f(e)}\).

Trees

A tree is a type of structure in which each element refers to a set of the “child elements” according to specified rules.

The following table lists some variations of the tree structures that are generalized and are used in some applied fields.

Tree Type	Description
Binary Tree	Each node has at most 2 children (left and right).
Binary Search Tree (BST)	Binary tree with left < root < right property for all nodes.
AVL Tree	Self-balancing BST with balance factor constraint (−1, 0, 1).
Red-Black Tree	Self-balancing BST with color-based rules to ensure balance.
B-Tree	Generalized BST used in databases and filesystems; supports multiple keys.
B+ Tree	B-Tree variant where all values are stored at leaf level for fast access.
Heap (Min/Max)	Complete binary tree with heap property (min or max at the root).
Trie (Prefix Tree)	Tree used to store strings with shared prefixes efficiently.
Segment Tree	Used for range queries and updates on arrays; stores intervals.
Fenwick Tree (BIT)	Compact structure for cumulative frequency queries and updates.
Suffix Tree	Compressed trie for all suffixes of a string; used in string matching.
N-ary Tree	Each node can have up to N children; generalization of binary trees.
Quad Tree	Each node has 4 children; used in 2D spatial indexing.
Octree	Each node has 8 children; used in 3D space partitioning.
Merkle Tree	Hash tree used in cryptographic applications and blockchain.

The most popular and possibly the most useful tree-type data structure is the binary search tree. For more information, check out the Binary search tree page.

Definitions

There are a few common definitions that are typically used in trees context:

Term	Definition
Node	A fundamental unit of a tree that contains a value and links to its child nodes.
Root	The topmost node in the tree. It has no parent. Every tree has exactly one root.
Leaf	A node that has no children.
Parent	A node that has at least one child
Child	A node that is directly connected and one level below another node.
Sibling	Nodes that share the same parent.
Subtree	Any node and all of its descendants form a subtree. The left and right children of a node each define subtrees.
Depth (of a node)	The number of edges from the root to the node. The root has depth 0.
Level	All nodes that are the same number of edges away from the root. The root is at level 0.