Help for Binary Search Tree (String Comparison)

[OlympicDreamer]

This is a project for assessment to enrol in a university.

My problem is, I am not really show whether my understanding of a binary search tree is the same as the university's.

My understanding is that I have to file strings as leaves under the root, and child leaf under parent leaf.

My questions is, do I assign numbers to alphabets from a-z. Then compare the number size of every alphabet between string A and B?

I have seen other examples of binary search trees and they don't do it like I think they do!

Help please!

 

[BlackCube]

There's a lot of different kind of implementation for BST.

You have to use a data structure to represent each node.

Read Binary tree - Wikipedia, the free encyclopedia

 

[davidktw]

This is a project for assessment to enrol in a university.

My problem is, I am not really show whether my understanding of a binary search tree is the same as the university's.

My understanding is that I have to file strings as leaves under the root, and child leaf under parent leaf.

My questions is, do I assign numbers to alphabets from a-z. Then compare the number size of every alphabet between string A and B?

I have seen other examples of binary search trees and they don't do it like I think they do!

Help please!

When you said your understanding, is it stated in the question that you have to use a binary searching algorithm to perform string comparison or you have to use a BST ? It is 2 different thing altogether.

To my knowledge, one of the best algorithm in string comparison is not related to any binary searching algorithm or any of its variants. Not that you can't use a binary search algorithm to perform string comparison, just don't understand how is it advantages to fast string comparison.

If binary search algorithm has to be applied, then the following will be how I would attempt it.
I don't see the need for a BST structure. It is more like you pass the 2 strings for comparison within a recursive binary search function. Using 1 string as reference, test on the middle character against a character from the other string at the same index. If it pass, then divide and conquer, partition the string into 2 halves, repeat select the middle character from each of the 2 halves string now.

Boundary cases you will need to take care, unequal strings length and empty string length.

 

[OlympicDreamer]

When you said your understanding, is it stated in the question that you have to use a binary searching algorithm to perform string comparison or you have to use a BST ? It is 2 different thing altogether.

... ...

Boundary cases you will need to take care, unequal strings length and empty string length.

The below is an extract of the question

In Node.java and BSTree.java you are given skeleton code for a binary search tree,
where each node contains a string. Nodes to the left are less and to the right greater.
In addition you are given a program Tree.java that allows you to "test out" a binary
search tree, and also draw a schema of that tree (the structure but not content).
You will also find power point lecture slides and data sets of various size.

I am assuming it is a string-string comparison because binary-binary doesn't make sense and from the examples shown it seems to be string-string.

Since java does not have a comparison/ranking table for alphabet and string comparison, my idea is to assign values 1 to the alphabet(key) A and 26 to alphabet(key) Z. Having said this, do you think I am on the right track?

 

[davidktw]

I am assuming it is a string-string comparison because binary-binary doesn't make sense and from the examples shown it seems to be string-string.

Since java does not have a comparison/ranking table for alphabet and string comparison, my idea is to assign values 1 to the alphabet(key) A and 26 to alphabet(key) Z. Having said this, do you think I am on the right track?

We are always comparing binary to binary for anything. What so special about String comparison nowadays with the involving of unicode is there exist multiple unicode index of characters where effectively they are the same character from a language semantics.

What ranking table are you looking for ? The String.compareTo method gives the lexical comparison between the 2 string arguments.

Based on what you have provided so far in this thread, both your explanation that you need to perform BST string comparison and also a snippet of your question, it is still not apparent what kind of comparison you are performing.

What I can understand is you are given Node.java, which you can easily overwrite certain methods to implement your own comparison for like the Object.hashCode method, the Object.equals method and so forth. Node objects will be thrown into the BSTree.java, which function as a BST data container. Tree.java is probably your main execution class.

It sounds like you need to compare 2 BST for same set of Strings, am I right ?