I'm looking for some examples of tree structures that are used in commercial/free software projects, modern or old. I can see examples on wikipedia, but I am looking for more concrete examples and how they're used. For example primary keys in databases are (from what I've read) stored in BST structure or a variation of the BST (feel free to correct me on this)
My question isn't limited Binary Search Trees (BSTs), it can include any variation such as red-black, AVL and so on.
Database indexes are normally stored as variamts of B* trees which, despite their name are not binary trees.
Is it okay if the examples are a tad bit generic i.e. relate to graphs and not necessarily to trees? If it is, read on.
Needless to say most XML/Markup parsers use trees. See Apache Xerces for example. Or, the Xalan XSLT parser. Thanks mathewsdave26 for reminding me!
PDF is a tree based format. It has a root node followed by a catalog node(these are often the same) followed by a pages node which has several child page nodes. Producers/consumers often use a balanced tree implementation to store a document in memory.
Computer chess games build a huge tree (training) which they prune at runtime using heuristics to reach an optimal move.
Flare is a visualization library written in AS. You may want to check out how the data objects are mapped. In particular the flare.analytics package heavily uses a graph structure, spanning trees etc.
Social networking is the current buzzword in CS research. It goes without saying that connections/relations are very naturally modeled using graphs. Often, trees are used to represent/identify more interesting phenomena. How do you answer questions like "Does Harry and Sally have any common friend(s)?"
Some very successful physics/games engines build trees to accurately simulate human movement. A tree in this case will typically correspond to a set of actions; The context will determine which path is taken to render a particular response.
Decision Tree based Learning actually forms a formidable area of data mining research. Numerous famous methods exist like bagging, boosting, and modifications thereof which work on trees. Such work is often used to generate a predictive model.
A common problem in bioinformatics is to search huge databases to find matches for a given query string. Tries are a common occurrence there.
Quite a few successful (stock) traders use decision trees in their day to day trading -- to choose a trade, to exit one. Often times these are not codified in a computer program, but written down somewhere on the back of their notebook.
The B in database index B* trees stands for Balanced, not Binary. The tree is kept at a uniform depth to ensure even access times.
Looking at any of the Datawarehousing products you'll see clever ways of storing and drilling into tree shaped dimensions. You get a tree structure for location (country, region, state,m county, town, etc) and time (Year, Month, Day, Hour). Those two dimensions are common across many domains, but much other real world data also lends itself to the tree.
For instance in food retailing, at the root of the tree you could have groceries, that can drill down into dairy, fruit & veg etc. Following a single thread you could have. Tins of beans, at the top level you'll be talking in lorry loads, then you'll come down to pallets, boxes, tin sizes. All of the different SKU (stock keeping units) are important to someone within the store or company. Then different types of beans, different suppliers, manufacturers - all examples of trees for the same dimension.
All of the different products form a massive tree, with different ways of slicing and dicinng.
C++ includes a number of collections (set, multi_set, map, multi_map) which are normally implemented as red-black trees, a kind of balanced tree.
(The C++ standard does not explicitly require this implementation, but this is the simplest design that meets the complexity requirements.)
In my project, an edit and imputation system for survey/census data, we use a binary decision tree to decide what variables of a record to impute or not impute. The binary decision tree allows us to efficiently make decisions about paths on the tree we should and should not take.
I think this approach (though maybe not just binary trees) is used in artificial intelligence applications as well
Binary Trees have been used for Space Paritioning and Hidden Surface removal on 3D games of old, I believe that one was used in the game Doom.
In a router/switch place I used to work we used a bunch of tree structures, for the software route table we used a radix tree (pretty common choice for a IP routing table).
Our OSPF implementation made use of red-black trees, our BGP implementation made use of skiplists.
Technically skiplists aren't tree structures but they are in practice very similar, and they're really cool.
We definitely used heaps quite a bit as well thinking on it, it's been a while since I worked there.
System.Collections.Generic.SortedList<T> uses a binary search tree as the underlying implementation. The same is true for System.Collections.GenericSortedDictionary<T>. Any code using SortedList<T> or SortedDictionary<T> is using a binary search tree.
Write a simple recursive-descent parser, and have it generate a parse tree.
Bill-Of-Materials structure used in manufacturing (like an automobile consists of subassemblies, recursively, down to the nuts and bolts).
Symbol table (as used in a compiler).
Chart Of Accounts as used in project management. An overall project has subprojects, to which charges can be applied.
Company organizational structure: divisions, departments, etc.
Table of Contents for a document.
Descendents of a person, ancestors of a person.
Any Lisp s-expression, including any Lisp program.
We use a tree structure to model a part classification system. Parts are classified into 'classes' which have parent classes and so on. The top-level classes drive the text for tabs in our catalog UI. Classes are also used to apply pricing rules, identify 'hot spots' on a vehicle where parts are displayed in a 'configurator', etc. We model the tree in SQL using Joe Celko's nested sets and load them on-demand into memory for better performance. The most common queries we make are 'who are my descendents' and 'is this class an ancestor of mine?'
Very handy
Auto-complete features in software (eg. search engine "suggestions", IDE type/symbol completion, email and address book names, etc) are often implemented as Tries, which are tree structures.
You guys all missed a biggie.
A special type of balanced binary tree is perfect for text editors.
There is a treap implemented in ActionScript. Sources:
The treap is part of the AS3Commons Collections framework. A modified treap is used to back the included SortedSet and SortedMap collections.
Classification of objects in general is very often done using trees. And very often, a graph would be much more suitable than a tree, however a tree offers two big advantages over a graph: