Trees
I started reading up on trees on Wikipedia using
this template. Here is summary of my findings so far:
Cartesian tree
A Cartesian tree is associated with a particular ordered list of numbers. Has the property that it is a binary heap (each node is smaller than all of its children) and reading it in symmetric order produces the associated ordered list.
It is useful when you need to find the minimum value in a contiguous sub-sequence of a list. If the list is structured as a cartesian tree than finding the minimum value between two nodes becomes the somewhat faster problem of finding the deepest common parent of the two nodes.
Top tree
The description of the top tree was quite technical but the basic idea seemed to be a dynamic representation of a rootless tree/forest.
T-tree
A T-tree is similar in purpose to a B-tree but it is a balanced binary tree. Each node in a T-tree contains links left right and up as well as a two boundary values and a list of values with some predefined minimum and maximum length.
AVL tree
An AVL tree is a self-balancing BST (binary search tree, meaning nodes are sorted if read in symmetric order). The idea behind an AVL tree is that it can remain balanced (ensuring a consistently logarithmic access time) by recursively rotating sub-trees.
Red-black tree
A red-black tree is another self-balancing BST with the following properties:
- Each node is either red or black.
- The root is always black.
- All leaves are black.
- Both children of each red node are black.
- Every descending path from a given node to any of its descendant leaves contains the same number of black nodes.
Like AVL trees, operations are generally performed in logarithmic time but the alternating red black nature of the tree allows means that rotation operations only need to be performed about half as often in exchange for the tree being slightly less rigorously balanced.
The Wikipedia article did a good job of explaining this and and I feel like with a little review I could definitely implement one of these if I needed to.
AA tree
An AA tree is a red-black tree in-which a red node can only be the left child of its parent and not the right. This simplifies the maintenance that is necessary. It's performance is generally about the same as a normal red-black tree.
Splay tree
A splay tree tree is a self-adjusting BST with the property that recently accessed elements are quick to access again. The basic idea is that after any given element is accessed, a series of rotations is performed to bring that element to the root. The rotations can also be performed as the tree is traversed in the first place. Unlike a self-balancing tree, a splay tree is not always balanced but recently accessed nodes will always be quite close to the root.
I think it would be interesting to implement one of these and then use graphviz to visualize the way it rearranges itself. I'm considering doing this over break.
Treap
A treap is a Cartesian tree that uses key randomization method to produce a structure that is statistically likely to be searchable in logarithmic time.
