PHP Classes

LLRB Tree: Manage a balanced tree of text word nodes

Recommend this page to a friend!
     
  Info   View files Files   Install with Composer Install with Composer   Download Download   Reputation   Support forum   Blog    
Ratings Unique User Downloads Download Rankings
Not enough user ratingsTotal: 906 All time: 3,918 This week: 455Up
Version License PHP version Categories
llrbtree 1.0Custom (specified...5.2PHP 5, Data types
Description 

Author

Jay Wheeler

This package can be used to manage a balanced tree of text word nodes.

It implements a left leaning Red-Black binary search tree that uses Node objects instead of arrays to implement the tree data structures.

It can perform operations on nodes of text words like insert, search, delete and traverse the tree, maintaining a balanced and correctly formed tree after each operation. This makes it perfect for creating efficient symbol tables and dictionaries.

Innovation Award
PHP Programming Innovation award nominee
August 2009
Number 6

Prize: One copy of VS.PHP		 Red-Black trees are data structures are self-balancing trees that can be used to implement binary search algorithms.

This class provides a pure PHP implementation of this kind of trees.

Manuel Lemos
Picture of Jay Wheeler
Name: Jay Wheeler <contact>
Classes: 1 package by
Country: United States United States
Innovation award
Innovation award
Nominee: 1x

Details

This work is based on algorithms developed by 

  D. E. Knuth, The Art of Computer Programming, 
    Vol. 3, Sorting and Searching, Addison–Wesley, 
  
  Robert Sedgewick, Left-leaning Red-Black Trees
    (http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf)

  Robert Sedgewick, 2008 International Conference on the Analysis of Algorithms in Maresias, Brazil 
    (http://www.ime.usp.br/~cris/AofA2008/slides/sedgewick.pdf)

  Files folder image Files (9)  
File Role Description
Plain text file bNode.php Class Binary node abstract base class
Plain text file bTree.php Class Binary tree abstract base class
Plain text file iComparable.php Class An interface to compare two objects
Accessible without login Plain text file License Lic. Statement of Copyright
Plain text file LLRBNode.php Class Implementation of the bNode class for LLRB nodes
Plain text file LLRBTree.php Class Implementation of the bTree class for LLRB Tree
Accessible without login Plain text file ReadMe Doc. Short description of the source of (most) of the algorithms
Accessible without login Plain text file testLLRBTree.php Example A test application to prove the correct operation of the LLRB tree
Accessible without login Plain text file testLLRBTreeResults Output Sample output from running testLLRBTree.php

The PHP Classes site has supported package installation using the Composer tool since 2013, as you may verify by reading this instructions page.
Install with Composer Install with Composer
Downloadllrbtree-2009-07-16.zip 13KB
Downloadllrbtree-2009-07-16.tar.gz 10KB
Install with ComposerInstall with Composer
 Version Control Unique User Downloads Download Rankings  
 0%
Total:906
This week:0
All time:3,918
This week:455Up

  Applications that use this package  
No pages of applications that use this class were specified.

Add link image If you know an application of this package, send a message to the author to add a link here.


  Pages that reference this package  
Robert Sedgewick (Department of Computer Science, Princeton University) published a very good algorithm, complete with detailed explanation, of creating and maintaining 2-3 and 2-3-4 binary trees, called Left Leaning Red Black Binary Trees (LLRB)...

Latest pages that reference packages Latest pages that reference packages