Binary Search Tree Node Lookup

The binary search tree has no index, so for the search operation on the binary search tree, a contain method is defined here to determine whether the binary search tree contains a certain element, returning a boolean variable. This search operation is also a recursive process. The specific code implementation is as follows:

...
// Check whether the binary search tree rooted at node contains a node with key value key, using recursive algorithm
private boolean contain(Node node, Key key){

if( node == null )
return false;

if( key.compareTo(node.key) == 0 )
return true;
else if( key.compareTo(node.key) < 0 )
return contain( node.left , key );
else // key > node->key
return contain( node.right , key );
}
...

The following example searches for element 43 in the binary search tree.

(1)Element 43 is greater than the root node 42, so it needs to continue comparing at the right child node.

(2)Element 43 is smaller than 59, so it needs to continue comparing at the left child node.

(3)Element 43 is smaller than 51, so it needs to be compared further in the left child node.

(4)Find the left child node 43 of 51, which is exactly equal, and the process ends.

If you need to find the value corresponding to the key, the code is as follows:

...
// Find the value corresponding to key in the binary search tree rooted at node, recursive algorithm
// Return NULL if the value does not exist
private Value search(Node node, Key key){

if( node == null )
return null;

if( key.compareTo(node.key) == 0 )
return node.value;
else if( key.compareTo(node.key) < 0 )
return search( node.left , key );
else // key > node->key
return search( node.right, key );
}
...

Java Example Code

Source Code Package Download:Download

src/example/binary/BinarySearchTreeSearch.java file code:

package example.binary;

/**
* Binary Search Tree Search
*/
public class BinarySearchTreeSearch<Key extends Comparable<Key>, Value> {
// The nodes in the tree are a private class; the outside world does not need to know the specific implementation of the binary search tree nodes
private class Node {
private Key key;
private Value value;
private Node left, right;

public Node(Key key, Value value) {
this.key = key;
this.value = value;
left = right = null;
}
}
// Root node
private Node root;
// Number of nodes in the tree
private int count;

// Constructor, constructs an empty binary search tree by default
public BinarySearchTreeSearch() {
root = null;
count = 0;
}

// Return the number of nodes in the binary search tree
public int size() {
return count;
}

// Return whether the binary search tree is empty
public boolean isEmpty() {
return count == 0;
}

// Insert a new (key, value) data pair into the binary search tree
public void insert(Key key, Value value){
root = insert(root, key, value);
}

// Check whether the key exists in the binary search tree
public boolean contain(Key key){
return contain(root, key);
}

// Search the binary search tree for the value corresponding to the key. If the value does not exist, return null
public Value search(Key key){
return search( root , key );
}

//********************
//* Helper functions for the binary search tree
//********************

// Insert node (key, value) into the binary search tree rooted at node, using recursive algorithm
// Return the root of the binary search tree after inserting the new node
private Node insert(Node node, Key key, Value value){

if( node == null ){
count ++;
return new Node(key, value);
}

if( key.compareTo(node.key) == 0 )
node.value = value;
else if( key.compareTo(node.key) < 0 )
node.left = insert( node.left , key, value);
else // key > node->key
node.right = insert( node.right, key, value);

return node;
}

// Check whether the binary search tree rooted at node contains a node with key value key, using recursive algorithm
private boolean contain(Node node, Key key){

if( node == null )
return false;

if( key.compareTo(node.key) == 0 )
return true;
else if( key.compareTo(node.key) < 0 )
return contain( node.left , key );
else // key > node->key
return contain( node.right , key );
}

// Find the value corresponding to key in the binary search tree rooted at node, recursive algorithm
// Return NULL if the value does not exist
private Value search(Node node, Key key){

if( node == null )
return null;

if( key.compareTo(node.key) == 0 )
return node.value;
else if( key.compareTo(node.key) < 0 )
return search( node.left , key );
else // key > node->key
return search( node.right, key );
}
}

other extensions