Quick Index
Function Tips


Note that the examples (in the next sections below) use pseudocode.

Sort Function (sortFct) in Java


First, let's look at the sortFct in pseudocode (from examples below):

r = sortFct(newCustomer, customer1)
//Result r is < 0, =0, or > 0

In Java, because sortFct is a Comparator, the pseudocode above would look similar to this:

int r;
r = sortFct.compare(newCustomer, customer1);
//Result r is < 0, ==0, or > 0

Nodes Want Data - Not Node


Our code may be hanging onto nodes, if so the above samples would look like this:

//Pseudocode
r = sortFct(newNode.getData(), customer1.getData());
//r is < 0, =0, or > 0
 

//Java
int r;
r = sortFct.compare(newCustomer.getData(), customer1.getData());
//r is < 0, =0, or > 0

Search Function (searchFct) in Java


First, let's look at the searchFct in pseudocode (from examples below):

r = searchFct(searchKey, customer1)
//Result r is < 0, =0, or > 0

In Java, because searchKey is a BiFunction, the pseudocode above would look similar to this:

int r;
r = searchFct.apply(searchKey, customer1);
//Result r is < 0, ==0, or > 0

Nodes Want Data - Not Node


See discussion above "Data - Not Node" under sortFct also applies to searchFct, i.e., if you have a handle to a node, use aNode.getData().

Sort Function


The BST should have sub-component (ivar) named "sortFct" to be used for sorting (e.g., when elements are inserted into the tree).

The search function 
 sortFct(elem1, elem2)
 returns an integer:

ConditionFunction
Result
if "key" sorts before "elem"< 0
if "key" matches "elem"= 0
if "key" sorts after "elem"> 0


We have the tree of customers shown sorted by name.

Inserting
Let's say we are adding a new customer with name "Awusi". We use sortFct with variable "newCustomer".

//Step #1
r = sortFct(newCustomer, customer1)
//r is < 0, so we continue search left

//Step #2
r = searchFct(newCustomer, customer2)
//r is > 0, and right is null
//Thus, we insert newCustomer to right
 
                 
1
Customer1
               (name="Chin")
                    |
      --------------+--------------
      |                           |
  
2
Customer2                   Customer3
(name="Asha")               (name="Riya")
                                  |
                             -----+
                             |
                         Customer4
                        (name="Kofi")
Inserting Finish
The new customer "Awusi" in the proper (sorted) position in the tree, thanks to the sort function.
                 Customer1
               (name="Chin")
                    |
      --------------+--------------
      |                           |
  Customer2                   Customer3
(name="Asha")               (name="Riya")
      |                           |
      +----                  -----+
          |                  |
      Customer5          Customer4
   (name="Awusi")      (name="Kofi")


Search Function


The BST should have sub-component (ivar) named "searchFct" to be used for searching.

The search function 
 searchFct(key, elem)
 returns an integer:

ConditionFunction
Result
if "key" sorts before "elem"< 0
if "key" matches "elem"= 0
if "key" sorts after "elem"> 0


Example 1
We have the tree of customers shown sorted by id.

We search for searchKey=30

r = searchFct(searchKey, customer1)
//r is > 0, so we continue search right
r = searchFct(searchKey, customer3)
//r is < 0, so we continue search left
r = searchFct(searchKey, customer4)
//r = 0, so we have match and return customer4
 
                      Customer1
                       (id=20)
                         |
           --------------+--------------
           |                           |
       Customer6                   Customer3
        (id=10)                     (id=40)
           |                           |
    -------+-------             -----+
    |             |             |
Customer5      Customer2    Customer4
 (id=5)        (id=15)       (id=30)
Example 2
We have the tree of customers shown sorted by name.

We search for searchKey="Riya"


r = searchFct(searchKey, customer1)
//r is > 0, so we continue search right
r = searchFct(searchKey, customer3)
//r = 0, so we have match and return customer3
 
                 Customer1
               (name="Chin")
                    |
      --------------+--------------
      |                           |
  Customer2                   Customer3
(name="Asha")               (name="Riya")
                                  |
                             -----+
                             |
                         Customer4
                        (name="Kofi")































Data Structures And Algorithms (DSA) (Chapter 702 - Binary Search Tree (BST) Concepts)










Chapter 702 - Binary Search Tree (BST) Concepts Sort and Search Functions

Index Video Intro Tree Node Operations Traversal Balance Iterators Design Pros Refs

Chapter Top Search Site Contents