Binary Search Tree
1. It is a tree.
-
There is a Parent-Child relation
for nodes.
-
There is only one root.
-
Each node has several children.
-
Each node has unique parent.
-
There is no cycle.
2. It is a binary tree.
a tree with every node having at most
two
children.
3. It is a search tree.
-
It is a “tree structure” storing values in the nodes.
-
It is organized in a nice way for traveling information.
-
The value in the left subtree is smaller
than the root value of that subtree;
the value in the right subtree
is larger than the root value of that
subtree.
Every node x (node
itself, i.e. actual record, or pointer to that node)
has the following information:
· key[x] - value stored in
x.
· left[x], right[x]
· parent[x]
Property:
If
y
is in left subtree of x then key[y] <= key[x]
If y
is in the right subtree of x then key[y] >= key[x]
Example of Binary Search Tree
Operations on Binary Search Tree (BST):
Click here to see a page produced by Chris Nevison
Click here to see building tree from Ford and Topp
*Read a data file into a Binary
Search Tree, traversal by inorder, release memory boxes at the end.
*old version
Data.dat