Data Structures: Trees

A tree in general is a data structure where each node has some particular number of children. A child node of another node (called the parent node) is a node the parent points to.

Binary Search Trees

A binary tree is a tree in which each node has at most two children, generally called the left child and right child. The root is the top node, and the leaves are all nodes without children. A binary search tree is a binary tree in which elements are kept in a particular order (this order is defined below).

The height of a binary search tree is the number of rows it contains (in the above photo, the height is $4$). Also, a subtree is a tree contained within another tree. For example, this tree has many subtrees: one rooted at $B$, one rooted at $C$, even one rooted at $M$.

For binary search trees, we add elements using the following recursive algorithm: suppose we want to add $n$ to the tree. Look at the value in the tree's root. If it's $\ge n$, then perform this algorithm on the tree rooted at its left child; if it's $<n$, then perform this algorithm on the tree rooted at its right child. Essentially, we are going down the binary tree, going left when our value is smaller than the node and right when it's bigger. See the following video:

The advantage of doing it this way is it keeps it in a logical order that provides quick insertion and searching. However, as of now this structure isn't extremely powerful yet: in the worst case, we keep on inserting numbers to the right all the time, which gives the same behavior as a linked list. That's why there's a need for an improved version: the AVL tree.

AVL Trees

AVL trees are a type of binary search tree that adjusts its height to be as even as possible at every step. It does this by performing tree rotations. While it's interesting to know about, it's not too important, so you can watch the video below if interested.

What is special about AVL trees is that never end up looking at this worst case example above, as the height of the left and right subtrees of each node can only differ by at most one. This guarantees that we can add elements in $O(\log n)$ and search elements in $O(\log n)$ too.

Short and sweet definition: A tree is a connected acyclic graph.