Archive for the 'Data Structures' category

The Basic Balanced Search Tree: Red-Black trees.

May 28 2008 Published by under Data Structures

During my Haskell tutorial, I used balanced binary search trees as an example. I've had people write to me asking me to write about that in a non-functional
programming post, because the Haskell one got too tied up in how to do things
without assignments, and with tail recursion.

Binary search trees (BST) are another one of the really fundamental simple data
structures. They're conceptually similar to heaps - they're also a kind of size-ordered binary tree with O(lg n) performance - but they've got a different set of basic invariants to represent the different performance goals.

The goal of a structure like a BST is to have a variable-size stucture where
you can cheaply and easily increase or decrease the size of the structure,
and where insert, delete, and searching for values are all inexpensive. BSTs
are a good choice for implementing things like dictionaries, where you have a key associated with a value, or where you want to be able to search for an arbitrary member quickly.

BSTs are very widely used - for example, the default ordered collections, sets, and maps in the C++ standard libraries are all implemented as a kind
of BST (in fact, the very kind that I'm going to describe below.)

If you have a meaningful ordering operation, then a BST is a good choice: expanding and contracting the structure happen automatically every time you do an insert or remove; and insert, delete, and search are all bounded by lg(n), where N is the number of values in the tree.

Continue Reading »

19 responses so far

Implementing Compact Binary Heaps

Apr 29 2008 Published by under Data Structures

Last post, I described the basic idea of the binary heap data
structure. But I didn't talk about how to implement it - and there's
a very cool way of implementing it - optimally space efficient,
very fast, and with respectable cache locality for moderate sized
datasets.

Continue Reading »

24 responses so far

Binary Heaps

Apr 28 2008 Published by under Data Structures

One of the most neglected data structures in the CS repertoire is
the heap. Unfortunately, the jargon is overloaded, so "heap" can mean
two different things - but there is a connection, which I'll explain
in a little while.

In many programming languages, when you can dynamically create
objects in memory, the space from which you allocate the memory to
create them is called the heap. That is not what I'm talking about.

What I am talking about is an extremely simple but powerful structure
that is used for maintaining a collection of values from which you want
to be able to quickly remove the largest object quickly. This may sound
trivial, but this turns out to be an incredibly useful structure. You can use this basic structure to implement a very fast sorting algorithm; to maintain a prioritized set of values/tasks; to manage chunks of memory; etc. (The
prioritized set is the most common case in my experience, but that's probably because I've spent so much of my career working on distributed systems.)

Continue Reading »

34 responses so far

« Newer posts