Skip to main content

Types of trees

Now for a forest of trees.

Trees are likely the most varied of all data structures.  There are specialized trees for applications in computer graphics, astrophysics, engineering, text processing, databases, and compression (just to name a few).  Trying to categorize trees into a small number of bins is somewhat pointless but I'll describe some of the broader types.

First some terminology.
The top of the tree is the root.  This is the only node in the tree which has no parents.
The parent of a node is the node which is higher in the tree.  A node will only ever have one parent.
The children of a node are all the nodes which are connected and one step lower in the tree.
An interior node is one which has both a parent and at least one child.
A leaf node is one which has no children.
The height of a tree is the distance from the root to the lowest child.
The depth of a node is the distance from the root to that node.

Now for some distinguishing characteristics of trees.

What is the maximum number of children which a node can have?
Some common numbers of children are
2 - binary tree
4 - quadtree
8 - octree
N - kd-tree, n-ary tree, radix tree, etc...

Do interior nodes hold elements?
A standard binary search tree stores its elements at every node whereas a red-black tree stores elements only as children.

How do we access/insert nodes?
There are many binary trees which differ only in the manner in which nodes are inserted.
Balanced trees rotate their nodes to keep the tree balanced.
Splay trees optimize themselves based on the access pattern.
Heaps reorganize themselves to keep the largest/smallest node at the root.

Some of the specialized trees are,
Barnes-Hut quad-trees which are used for astrophysics simulation.
Huffman coding trees which are used in compression.
BSP trees for computer graphics.
B* trees which are used in databases.

You could easily spend years studying nothing but trees.


Labels:

Comments

Post a Comment

Popular posts from this blog

Duck typing considered harmful.

I've had a chance to work on a fairly large chunk of Python at this point and have decided that Python (like Perl) is completely untenable at scale.  <rant><rave><drool>  but wait!  I have reasons! Programmers spend most of their time reading code.  We read massive amounts of code.  After we read massive amounts of code we write one... or change one... To make a change to a piece of code you first have to understand what it does and how it interacts with the system around it.  Then we start reading massive amounts of code again.  Anything you can do to minimize the amount of code a programmer has to understand to make a change becomes a huge gain in productivity. Duck typing causes the amount of code you need to read to make a change to grow very large. For example lets look at two functions, one in C++ and one in Python. First in C++ int function(type1 arg1, type2 arg2) {   return arg1->method(arg2); } In this fun...
1 comment
Read more

Tamiya Tracks

So... a "buddy" of mine got me this for Christmas this year.   I figure... hey, what the heck!  I should be able to get in trouble with this! It makes a nice little vehicle that works quite well.  I hope to turn this into a cool little telepresence rover but during the course of assembly I realized something... No "friend" should every give you something with pieces like this! I am seriously not built for handling pieces that small!
Post a Comment
Read more

Segmented Sieve

Our next version works just like the previous sieve but works on a segment of the number line at a time. That might be why it is called a  segmented sieve . Now we are sieving multiples of the primes from 1M numbers at a time, adding those primes to the list and then moving on to the next 1M numbers. I hit 140M primes in 60 seconds on my box... but now I run into a new problem.  This version of the sieve quickly consumes all the memory in my box and slows to a crawl.  To progress we will need to find a more efficient way of storing the primes we have found.
Post a Comment
Read more