← back

2019-11-02: common tree data structures in programming

Tree structures have the advantage that they are able to organize (and potentially sort) large quantities of information by featuring nodes that branch out from some central starting point, and do so in a formulaic way. In particular there are many types of trees, including the B and A-B and R-B; along with search patterns like A* and the Monte Carlo tree search.

B-trees are tree structures that self-balance / self-sort and are designed in such a way as to allow for searches, access, insertions and deletions in logarithmic time. Typically they are used for situations that need to read and write large blocks of data, like databases or filesystems.

A-B trees are structures that have all of their leaves at the same depth and all internal nodes (except for the root) have between "a" and "b", where 2 <= a <= (b+1) / 2. The root has (if it is not a leaf) has between 2 and b children.

A red-black tree is similar in concept to the B-tree in that it is a kind of self-balancing binary search tree. Most notably each node contains an extra bit that stores whether it is "red" or "black".

In a red-black tree, the purpose of the colour is to ensure that the tree remains balanced during insertion and deletions. This feature constrains how unbalanced a tree can become in the worse case scenario, and admittedly while the algorithm is not perfect, it will nonetheless yield a search or insertion or deletion operation in O(n log n) time.

The A* searching is a graph traversal and path search algorithm which is a best-first search that is formulated in terms of weighted graphs. Starting from a specific node of a graph, it aims to find a path to the given goal node having the smallest distance or shortest time.

When implementing A* searching, a feature to consider is that this algorithm works by maintaining a tree structure of paths originating at the start node and extending these paths one edge at a time untils its termination criterion is satisfied; e.g. a certain distance or value.

Monte Carlo tree search is a heuristic search algorithm for decisioning, often used as part of an AI implementation in video games. Most famously it was used by Google Deepmind for their AlphaGo software.

In particular the Monte Carlo tree search relies on the Monto Carlo method which when combined with a search tree algorithm, allows for a way to store past and previous decisions in order to yield recursive rollout and backtracking and adaptive sampling choices for the final decision made by the AI.