When implementing data structures, its crucial to validate that your implementation is working as expected. A suite of tests is essential to not only debugging, but also optimizing performance one your implementation is correct. In the past I've discus
As computer architectures continue to evolve, data structures which were once considered well suited for one task may shift to become more applicable for a different task. One example of this is the family of balanced search tree's known as B-Trees. B-
In my previous post I went over one possible scheme for an Object structure suitable for implementing dynamic typing in an interpreter. Tha
The Skip List, introduced in 1990 by Pugh[1] is an interesting data structure. Skip lists came in to being as an evolution of the humble linked list. Indeed, skip lists have been described as "linked lists with a fast lane", which is certainly true, bu
The 1978 paper "A Dichromatic Framework for Balanced Trees" by Guibas and Sedgewick[1] in which the authors introduced red/black trees to the world, they discuss algorithms for bottom up 2-3 tree's, bottom up 2-3-4 tree's, and bottom up AVL tree's usin