Tuesday, October 9, 2012

Demonstrating usage of a Binary Search Tree in Java

What is a Binary Search Tree?

Binary Search Tree (BST) is a tree in which each node has up to two child nodes (subtrees).  If pointers are used, then each node contains references to the left, right, and parent nodes.  Otherwise, like the implementation I found for Java, each node contains a left and right subtree in the form of a left and right node (each of which have their own two subtrees and so on...) along with the data associated with the node.

A BST is said to have a binary-search-tree property:

Let x be a node in a binary search tree. If y is a node in the left subtree of x, then key[y] <= key[x]. If y is a node in the right subtree of x, then key[x] <= key[y].1

Since Java doesn't have pointers that we can use, we won't keep track of keys. We'll work directly with node data.

Cormen et-all mention that BSTs support the following operations:

Search trees are data structures that support many dynamic-set operations, including
SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, and
DELETE. Thus, a search tree can be used both as a dictionary and as a priority
queue.


What are some applications of BST?

This StackOverflow question answers this well:
What are the applications of binary trees?

Apparently, it is also used in the solution to the Traveling Salesman Problem and the related Shortest Path Problem. I'll be checking these out soon.


How do I use a BST in Java?

I found a good Java BST impl here:
BST.java
BSTNode.java

Class BST contains a root BSTNode node and provides most BST operations (as identified by Cormen et-all). The PREDECESSOR and SUCCESSOR operations are not implemented. Search is implemented, though not exposed directly (it's exposed as isInTree(T el)).

I've slapped together an Eclipse project that demonstrates the usage of this BST implementation. I added some code to BST.java (the one in the Eclipse project) borrowed from this Stanford CS Library page on BSTs. I also borrowed some inspiration from this SO page: How to print binary tree diagram. The class BTreePrinter in the project is pretty much directly from this SO page.

It would be worthwhile to study at least the BST.java and BSTNode.java.

>Download BST_Demo (Eclipse Project)

Here is the output:


>String arrays:
ACEG:  [Aliyah, Chris, Elijah, Gamal]
BDFH:  [Brian, Doug, Farah, Hasan]

>Insert ACEG:
Aliyah Chris Elijah Gamal 

>Insert BDFH:
Aliyah Brian Chris Doug Elijah Farah Gamal Hasan 

>Removing 'Aliyah':
Brian Chris Doug Elijah Farah Gamal Hasan Aliyah Brian Chris Chris Doug Elijah Elijah Farah Gamal Gamal Hasan 

>Clearing bst.

>Reinserting both arrays:
Aliyah Brian Chris Doug Elijah Farah Gamal Hasan 

>Search for 'Irene':
false

>Search for 'Aliyah':
true

>Postorder: 
Brian Doug Farah Hasan Gamal Elijah Chris Aliyah 
>Postorder (iterative): 
Brian Doug Farah Hasan Gamal Elijah Chris Aliyah 
>Postorder (Morris): 
Brian Doug Farah Hasan Gamal Elijah Chris Aliyah 

>Preorder: 
Aliyah Chris Brian Elijah Doug Gamal Farah Hasan 
>Preorder (iterative): 
Aliyah Chris Brian Elijah Doug Gamal Farah Hasan 
>Preorder (Morris): 
Aliyah Chris Brian Elijah Doug Gamal Farah Hasan 

>Size:
8

>Max depth:
5

>Min val:
Aliyah

>Max val:
Hasan

Aliyah Brian Chris Doug Elijah ElijahGamal Farah Gamal Hasan 

>Print all root-leaf paths:
Aliyah Chris Brian 
Aliyah Chris Elijah Doug 
Aliyah Chris Elijah Gamal Farah ElijahGamal 
Aliyah Chris Elijah Gamal Hasan 


>Mirroring bst:
Aliyah Brian Chris Doug Elijah ElijahGamal Farah Gamal Hasan 
Hasan Gamal Farah ElijahGamal Elijah Doug Chris Brian Aliyah 

>Doubling bst:
Hasan Hasan Gamal Gamal Farah Farah ElijahGamal ElijahGamal Elijah Elijah Doug Doug Chris Chris Brian Brian Aliyah Aliyah 

>bst:
Aliyah Brian Chris Doug Elijah Farah Gamal Hasan 
>bst2:
Aliyah Brian Chris Doug Elijah Farah Gamal Hasan 
>bst identical to bst2?:
true

>Possible unique trees given this bst's size: (8)
1430

>Check bst:
true

>Printing bst (bad spacing):
               Aliyah                               
                      \               
                       \              
                        \             
                         \            
                          \           
                           \          
                            \         
                             \        
                       Chris               
                      /      \       
                     /        \      
                    /          \     
                   /            \    
                   Brian       Elijah       
                          /       \   
                         /         \  
                         Doug   Gamal   
                            /      \ 
                            Farah Hasan 
                                                                

>Another bst print:
'- Aliyah
    '- Chris
        '- Brian
        '- Elijah
            '- Doug
            '- Gamal
                '- Farah
                '- Hasan

>Inst and init int bst (unbalanced because of ordered insert):
'- 1
    '- 2
        '- 3
            '- 4

Unbalanced integer tree:
       1               
        \       
         \      
          \     
           \    
           2       
            \   
             \  
             3   
              \ 
              4 
                                

Cleared and intBst.balance(intArr):
'- 2
    '- 1
    '- 3
        '- 4

>Balanced integer tree:
   2       
  / \   
 /   \  
 1   3   
      \ 
      4 
                


1 Introduction to Algorithms Second Edition (Cormen, Leiserson, Rivest, Stein), page 254

Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)