Trees
Trees are a special form of DAGs (Directed-Acyclic-Graphs) wherein each node (starting at the first/root) is connected to N other nodes (uniquely).
E.g. Here we have a tree, note how vertices on the same level do not connect to each other, but can share an ancestor.
graph TD; a-->b & c; b-->d & e & f; c-->g;
Implementation
Trees much like graphs, are often implemented in one of two ways.
- A set of elements, with a separate map containing the edges for each element to their children (called an “Adjacency List”).
- A node structure where the nodes themselves store a list of pointers to its children.
Balancing
Balancing a tree is the process of ensuring that the tree’s height is minimized so that operations on it can be performed efficiently. In a balanced tree, the depths of the left and right subtrees of any node differ by at most a small constant factor (usually 1). This prevents a tree from degenerating into a linear structure (like a linked list), which would cause inefficiencies. Unbalanced trees are often referred to as skewed.
Methods of Balancing
- Rotations: In trees such as AVL and Red-Black Trees, rotations are used when imbalances are detected during insertion or deletion.
- Rebuilding/Splitting: In some cases, the tree is partially or fully rebuilt when it becomes imbalanced.
Self Balancing Trees
Some tree structures are self-balancing.
- AVL Tree: Balances by maintaining a strict height difference of 1 between subtrees.
- Red-Black Tree: Ensures a “balanced enough” structure with colour-based partitioning/balancing rules.
- B-Trees (and B+ Trees): Used in DBs and file systems to keep trees balanced across multiple nodes, optimized for disk access.
Binary Tree
#data-structure#graph#tree#binary-tree
Binary trees are trees wherein each node has at most 2 children. graph TD; a-->b & c; b-->d & e; c-->f;Implementation Usually binary trees are implemented as a node with two pointers to its children.
Linked Lists
#data-structure#graph#linked-list#tree#queue#deque#stack
A link list is a special case of a tree, where each node is connected to at most one other node (singly-linked) or two other nodes (doubly-linked). Nodes can only ever be linked to the next node, or the next and the previous node. graph TB; subgraph "Doubly-Linked List" A<-->B<-->C<-->D; end subgraph "Singly-Linked List" a-->b-->c-->d; endSingly-Linked List Usage Efficient insertion/deletion at the front: O(1) for push_front and pop_front, which makes it ideal for a stack-like structure. Simple traversal: If you only need forward traversal, a singly-linked list is simpler and more space-efficient than a doubly-linked list. When space is a concern: Singly-linked lists are more memory-efficient than doubly-linked lists due to the single pointer per node. Stack: A simple stack can be implemented with a singly-linked list, where push and pop operations happen at the front. FIFO Queue: A first-in-first-out data structure like a queue is implementable as a singly-linked list. Where you push to the back, and pop from the front. Note, this only makes sense if you also keep track of the tail. Complexity Insertion at the front (push_front): $O(1)$ Insertion at the back (push_back): $O(n)$, since we must traverse the entire list to append. Deletion from the front (pop_front): $O(1)$ Traversal (print_list): $O(n)$ Space complexity: $O(n)$ due to the $n$ elements and pointers. Implementation Typically, implemented as a node structure where each node holds a pointer to the next node. Optionally, a pointer to the tail can be kept track of to be able to more efficiently insert at the back.