Tree Structure

From GPWiki
Jump to: navigation, search

Introduction

A tree is a data structure that can be likened to a linked list. The main differences is that where a linked list has one pointer reference in an element (pointing to the next element), a tree node can have many pointers, pointing to the 'children' of the element they are in. The simplest case of a tree (without the tree being a list) is where each tree node has 2 pointers, pointing to a 'left' subtree and a 'right' subtree. This is called a binary tree, and has many useful applications. There are also many variations on the tree theme, even with the most simplistic binary tree. Some examples are:

  • Ordered Binary Tree
  • Cyclic Binary Tree

Concepts

With trees, there are 2 important concepts that are always applicable. There is the tree 'traversal' which is an algorithm for visiting every element of a tree in some order, and there is tree 'balancing' which is an algorithm for changing the arrangement of the tree nodes so that the depth of the tree is minimal (the depth is the maximum number of nodes visited in order to reach a node with no children). These concepts are important to most tree structures, although the algorithms used for them will vary greatly depending on the exact tree used.

Uses

As for why you would use a tree, the main factors are that the speed of inserting, deleting and searching a tree are all O(d), where d is the depth of a tree (in the balanced binary case, this is log_2(N), rounded up). Compare this to a linked list, with O(N), where N is the number of elements in the list, and you can see an advantage with these basic operations. Also, the ease of a binary search on an ordered binary tree is a useful advantage when coding tree structures. In the cases of non-binary trees, there are several specific examples such as quadtrees and octrees for spatial data (4 and 8 children per node respectively), BSP trees (again for spatial data), B+ trees for filesystems and databases, and the general case of an N-ary tree (where each node can have a variable number of children). Applications beyond already stated are in AI, spatial enumeration, filesystems, databases, and any other system that needs a way of storing structured data.

Other Information

There are quite a few types of tree structures (balanced, red/black, octrees) that are optimized for different needs. An example of a balanced tree in VB 6 can be found here: [[1]].

Other Sources

Trees in Collision Detection