tree structures

There are several ways in which computer data can be compressed, stored on file and stored in memory. One such file compression technique is with the adoption of tree structures. Trees can be structured in numerous formats and have been well known for many years for their effective and efficient storing capabilities and their ability to accommodate fast searching of data. Trees can become unbalanced meaning that there are more node and depth on one side of the tree than the other which can make them inefficient data structures. There are of course various methods and algorithms which can be adopted to balance trees as they are being fed new data such as the relaxed balancing method or AVL tree algorithms. Binary tree structures are very good for storing data, which has to be searched quickly as this can be performed with tree structures faster than with such things as linked lists. 3 of these most basic and commonly used tree structures are:

Binary trees.
Quadtrees.
Octrees.

Binary trees

This tree structure has a root node, which is the first header node. Typically this type of tree structure is used frequently for storing names. The Binary trees can also be used to store numbers where the initial input data is held in the root node. Any subsequent data, which is fed in, will go to the left child if the number has a lower value than the root node and to the right child node if it has a greater value than the root node. Each time a number is passed in, it traverses down the nodes moving left or right when required until it finds its position in the tree. Each node can have up to two child nodes. Leaf nodes do not have any children and their parents are the header nodes directly above them in the hierarchal structure. Fig 1 below shows an example of a binary tree structure when the following sequence of values are fed in -

[7,10,12,8,5,3,6,11,13].

Figure 1

Quadtrees

Quadtrees are similar to binary trees except that instead of each node having up to a maximum of 2 child nodes, quadtrees can have up to a maximum of 4 child nodes. For the purposes of this research, quadtrees are used to store 2D images with each node containing an area of an image. If an area of the image has the same colour value it is said to be homogeneous. This data structure has a root node which is the first header node. If the colour value of this node is not homogeneous, this header node then points to 4 child nodes. The image is then broken up into 4 equal regions consisting of a top left region, a top right region, a bottom left region and a bottom right region. Each of the parent nodes children hold one of these regions. This process is repeated over and over again until all of the image is broken down in to regions of homogeneity. Again, these child nodes can be either header nodes themselves or leaf nodes. Leaf nodes do not have any children and their parents are the header node directly above them in the hierarchal structure. An example of a quadtree data structure is shown below in Fig 2.

Figure 2

Octrees

Octrees are similar to binary trees and quadtrees except that octrees can have up to a maximum of 8 child nodes. In this research octrees will be one of the main methods of storing 3 dimensional arrays. Octrees have a root node, which is the first header node. If the values of this node are not homogeneous, this header node then points to 8 child nodes. These child nodes can be either header nodes themselves or leaf nodes. Leaf nodes do not have any children and their parents are the header node directly above them in the hierarchal structure. An example of an octree structure is show in Fig 3 below.

Figure 3

Fig 4 below shows an example of a 2D bitmap made up of various colours. To store this image as a quadtree structure it is first broken up into homogeneous regions and this results in tree structure in memory as shown in Fig 5.

Figure 4

Figure 5

Click on the following link to see an animation of this bitmap being split up into homogeneous regions forming a quadtree structure. Quadtree animation. - (4.81MB)