Database Reference
In-Depth Information
A1.3 Threaded Binary Trees
In order to facilitate easy traversal of a binary tree, the tree may be threaded with pointers
that explicitly show a traversal ordering. The threads link the nodes in the sequence of
the traversal method.
Types of Threads:
Right thread links a node to its successor
•
•
Left thread links a node to its predecessor
A tree can only be threaded according to one traversal method at a time.
Threaded for In-order Traversal
To illustrate, if a binary tree is threaded for In-order processing, the following conventions
are observed:
Left threads (except for leftmost leaf ) point to predecessor nodes
•
in in-order.
•
Left thread from leftmost leaf points to the root.
•
Right threads (except for rightmost leaf ) point to successor nodes
in in-order.
•
Right thread of rightmost leaf is NULL.
A1.4 Binary Search Trees
A binary search tree (BST) is a binary tree in which the following properties hold:
a.
All nodes in the left sub-tree of R
i
precede (by way of ordering)
R
i
so that, If R
j
= R
i
.Left, then R
j
.Info < R
i
.Info
b.
All nodes in the right sub-tree of R
i
succeed (by way of
ordering) R
i
so that, If R
j
= R
i
.Right, then R
j
.Info >= R
i
.Info
Note:
In-order traversal of a BST produces a sorted list (in ascending values). Moreover,
it can be shown that this sort algorithm is an O(N Log N) algorithm on the average.
A BST provides the following advantages:
It facilitates an O(N Log N) sort, which is more efficient sort than
•
N
2
sort algorithms.
•
It facilitates faster (binary) search than searching a linear linked list.
The disadvantages associated with a BST are as follows:
It takes up more space than linear link list.
•
•
It can degenerate into a linked list (see next section).
•
As nodes are added, there is no control on the height (hence
structure) of the tree. This is often undesirable.
