Trees
Splay Tree
Self Balancing tree that caches
A splay tree moves recently searched for items to the root. The idea being that not all items are equally desireable. Ie. some items will be referenced more than others.
http://en.wikipedia.org/wiki/Splay_tree
http://cs.nyu.edu/algvis/java/SplayTree.html
http://cs.nyu.edu/algvis/java/SplayTree.html
Trie
String Dictionary
Dictionary Look up tree. Each node discovers one letter (or longer substring). Useful for spell checking. Word lookup takes no longer than length of the word. Data is naturally compressed. Abstraction can be used in other context.
http://en.wikipedia.org/wiki/Trie
http://www.nist.gov/dads/HTML/trie.html
B Tree
A non binary tree
In a b tree each node contains a list of values and links. Links to deeper nodes are found by searching the list. Not all nodes need to be full. The B tree has insert and delete operations that keep it balanced. The meaning of the B in B tree may come from one of 4 definitions. It was invented by Bayer at Boeing for use in Block devices and the variable determining the size of each node is traditionally b.
http://en.wikipedia.org/wiki/B-tree
http://www.bluerwhite.org/btree/
http://cis.stvincent.edu/carlsond/swdesign/btree/btree.html
http://www.semaphorecorp.com/btp/algo.html
http://www.semaphorecorp.com/btp/b1k.html
B-Tree animation applet
B+ Tree
A special form of the b tree
The B+ tree differes from the B tree in that all data is stored only in the leaf nodes. The search tree contains only keys
http://en.wikipedia.org/wiki/B+_tree
http://www.seanster.com/BplusTree/BplusTree.html
2-3 Tree
A balancing tree
A search tree. All interior nodes have 2 or 3 children. (No single child)
http://en.wikipedia.org/wiki/2-3_tree
http://www.aihorizon.com/essays/basiccs/trees/twothree.htm
2-3-4 Tree
A balancing tree
A B-tree of order 4. search tree. All interior nodes have 2 or 3 or 4 children. Isometric to red black tree which is apparently easier to implement due to the high number of exception cases.
http://en.wikipedia.org/wiki/2-3-4_tree
Red Black Trees
Self balancing tree
A binary search tree that colors it's nodes and defines 5-6 properties. By maintaining these properties the goal of balancing the tree is also served. A 2-3-4 tree and a red black tree have been determined to be equivalent.
http://en.wikipedia.org/wiki/Red_black_tree
http://www.cs.auckland.ac.nz/software/AlgAnim/red_black.html
http://www.nist.gov/dads/HTML/redblack.html
http://www.eli.sdsu.edu/courses/fall95/cs660/notes/RedBlackTree/RedBlack.html
http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/RedBlackTree-Example.html
http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic18/
AVL Tree
Self balancing Binary Search Tree
The AVL tree is like the redblack tree in that it is self balancing. Instead of defining a color for each node it defines a AVL value which is simply the difference in height between the left and right sub trees. By keeping this value at 0+/-1 the tree maintains a balanced structure.
http://en.wikipedia.org/wiki/AVL_tree
http://www.site.uottawa.ca/~stan/csi2514/applets/avl/BT.html
http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm
http://www.cs.jhu.edu/~goodrich/dsa/trees/avltree.html
http://sky.fit.qut.edu.au/~maire/avl/System/AVLTree.html
Useful Links
http://en.wikipedia.org/wiki/B-tree
http://en.wikipedia.org/wiki/B+_tree
http://www.bluerwhite.org/btree/
http://cis.stvincent.edu/carlsond/swdesign/btree/btree.html
http://www.semaphorecorp.com/btp/algo.html
http://www.semaphorecorp.com/btp/b1k.html
B-Tree animation applet
http://www.seanster.com/BplusTree/BplusTree.html
http://en.wikipedia.org/wiki/AVL_tree
http://www.site.uottawa.ca/~stan/csi2514/applets/avl/BT.html
http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm
http://www.cs.jhu.edu/~goodrich/dsa/trees/avltree.html
http://sky.fit.qut.edu.au/~maire/avl/System/AVLTree.html
http://en.wikipedia.org/wiki/2-3_tree
http://en.wikipedia.org/wiki/2-3-4_tree
http://www.aihorizon.com/essays/basiccs/trees/twothree.htm
http://en.wikipedia.org/wiki/Red_black_tree
http://www.cs.auckland.ac.nz/software/AlgAnim/red_black.html
http://www.nist.gov/dads/HTML/redblack.html
http://www.eli.sdsu.edu/courses/fall95/cs660/notes/RedBlackTree/RedBlack.html
http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/RedBlackTree-Example.html
http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic18/
http://en.wikipedia.org/wiki/Splay_tree
http://cs.nyu.edu/algvis/java/SplayTree.html
http://cs.nyu.edu/algvis/java/SplayTree.html
http://en.wikipedia.org/wiki/Trie
http://www.nist.gov/dads/HTML/trie.html