Binary Search Tree Tutorial

This tutorial will illustrate the use of Binary Search Trees in BRIDGES. BRIDGES supports hierarchy of tree elements, such general trees with arbitrary number of children, binary trees, AVL and K-D trees. Check the TreeElement class to see the full hierarchy. The BSTElement which denotes a node of the binary search tree is inherited from Element and has two generic parameters, one for the Key, which must be an orderable type and a second parameter, E, to hold application specific data.

BSTElement<K,E> is a container that has two links that point to two child BSTElements. It uses the same conventions as the TreeElement<E>.

You might wonder how a BSTElement<K,E> differs from a regular Binary Tree Element. The fundamental difference between the two classes is that the BSTElement<K,E> is used to build search trees, and holds an additional piece of data, the generic parameter K, called the "key". The key is used to enforce an ordering on the tree structure independent of the element that is being held.

A typical example would be a binary search tree where all of the keys of the left child are smaller than the keys of the right child.



Notice that the key for BST1 is smaller than the key for the root so it's to the left of the root. Also notice that the key for BST3 is smaller than the key for BST2, but larger than the key for the root. So BST3 sits on the left subtree of BST2, but in the right subtree of the Root.

This tutorial consists of 3 parts:

  1. A basic tutorial on how to create manually a small binary search tree and visualize it
  2. How to style the binary search tree with visual attributes
  3. Advanced: how to build a binary search tree automatically using an insertion function

See also

This tutorial gives an introduction to the usage of binary search trees. You can find the complete documentation of the features in the Doxygen documentation of the following classes and functions:

  1. BSTElement [Java] [C++] [Python]
  2. BinTreeElement [Java] [C++] [Python]
  3. Tree [Java] [C++] [Python]
  4. Element [Java] [C++] [Python]
  5. ElementVisualizer [Java] [C++] [Python]
  6. LinkVisualizer [Java] [C++] [Python]
  7. Color [Java] [C++] [Python]

1. Getting Started: Build a Barebones Binary Search Tree

In the first part of the tutorial, we will create a set of BSTElement nodes with some labels, , provide BRIDGES a handle to the data structure and visualize the array. Here is the code for this part. The visualization follows that. Hit the 'l' button to turn on the labels.

Java
C++
Python

Make sure that you can run the basic tutorial.

If you follow the URL given to you when the application runs, it will get to to the Bridges webpage that shows your output. You do not need to be logged into your BRIDGES account to see the output. If you are logged into your account, the output will show up in your gallery.

2. What Visual Attributes are supported for Binary Search Trees?

The binary search tree you created in the first part of the tutorial uses default attributes and is pretty boring, but it gives you the basic structure of a BRIDGES program.

Next, we will style the binary search tree we just created. For trees, , you can set the shape, color, opacity and label of the tree nodes, and color, thickness, opacity and label for the links. Check out the Bridges 'Element' and 'Color' classes that supports these attributes and also details the possible colors you can use and how to specify them.

The following code styles the binary search tree we created in part 1 and adds visual attributes. The visualization follows that.

Java
C++
Python

3. Advanced Features.

In the last part of this tutorial, we illustrate a search algorithm to find a specific value in the binary search tree. We also illustrate how the tree can be styled to show the nodes visited and the path taken by the search algorithm

The following code illustrates the search algorithm in a binary search tree. The visualization follows that.

Java
C++
Python

Well done! You’ve just created your Bridges Binary Search Tree project!

Going Further

Array2D and Array3D are similar in terms of the features. Try these tutorials with these structures.

Check Bridges assignment page for array based assignments