Since their inception, Binary Search Tree's have come to be one of the most fundamental data structures in programming. Shortly after their initial development it was realized that with a bit more work we could gurantee a worst case performance of loga
Sometimes when perusing the literature you come across an interesting algorithm, that while of dubious practical applicability, is none the less of novel interest. This post is about just such an algorithm. I can't be certain, but if i were to hazard a
It's no secret that when it comes to search structures, hash tables are fast. Performance wise, a hashtable can be much faster than any of the ordered search tree's frequently discussed in my posts. If your data doesn't require a
The relationship between binary search trees and linked lists is no secret. Without the use of some self balancing scheme any binary search tree has the potential to "devolve" into a linked list if subjected to a series of insertions in sorted order. I
Regular expressions and NFA have been an active area of study in theoretical computer science since the late 1950's. As such, there is a large body of work exploring a multitude of ways to evaluate regular expressions for the purpose of pattern matchin
-
The Aho, Sethi, Ullman Direct DFA Construction Part 2: Building the DFA from Followpos
-
The Aho, Sethi, Ullman Direct DFA Construction, Part 1: Constructing the Followpos Table
-
Procedural Map Generation with Binary Space Partitioning
-
Exact Match String Searching: The Knuth-Morris-Pratt Algorithm
-
The visitor pattern: OOP takes on the Expression Problem
-
Improving mgcLisp's define syntax
-
Separating the Men from the Boys, Knuth Style
-
Reducing rotations during deletion from AVL trees
-
Parsing Lisp: From Data To Code
-
Swiz Heaps: A deterministic modification of Randomized Meldable Heaps