Database Reference
In-Depth Information
A1.8 Summary and Concluding Remarks
Here is a summary of what has been discussed in this chapter:
•
A tree has one root and zero or more other sub-trees connected to
it. Except for the root, each node has a parent node.
•
A binary tree (BST) is a tree in which each node is either empty
or consists of two disjoint binary trees: the left sub-tree and the
right sub-tree. The BST may be traversed in-order, pre-order, or
post-order.
•
A binary search tree is a binary tree in which all nodes to the left
of a node are less then or equal to that node; all nodes to the right
of a given node are greater than or equal to that node.
•
A height-balanced k-tree (denoted (HB (k)) is a BST in which
the maximum allowable difference in height between any two
sub-trees sharing a common root (not necessary a parent) is k.
For AVL trees, k = 1.
•
A heap is an almost complete binary tree, such that: Every leaf of
the tree is at level m or m + 1, where m is an integer; if a node has
a right descendant at level l, it also has a left descendant at level l;
there is some established relationship between the parent-value
and its two children-values.
•
An m-way search tree is a tree of out-degree less than or equal to
m, i.e. a maximum of m pointers point from a node. The tree has
the following properties: Each node has a maximum of m pointers
and m-1 key values; in any node, the key values are in ascending
order; the pointer to the left of key value k[i] points to a node with
values less than or equal to k[i]; the pointer to the right of key
value k[i] points to a node with values greater than or equal to k[i].
•
A B-tree is a special type of m-way search tree with the following
properties: Except for the root and leaves, each node of the tree
has at least m/2 sub-trees and no more than m sub-trees; the root
of the tree has at least two sub-trees, unless it is itself a leaf; all
leaves of the tree are at the same level.
Trees (and particularly BSTs, heaps, and B-trees) are widely used in software
engineering to solve various programming problems related to the organization and
retrieval of data.
