4 Replies - 542 Views - Last Post: 30 November 2017 - 10:05 AM Rate Topic: -----

#1 chloeCodes  Icon User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 178
  • Joined: 05-January 17

Binary Search Tree with Strings

Posted 29 November 2017 - 03:31 PM

Hi there!

I am writing some explanation of algorithms that can be applied to BST data structure. I often find myself saying "greater" or "less than", but then I remember I'm dealing with Strings and not Integers! In my tree implementation I use the compare to method. Would it be more correct if I said "Lexicographically greater", that sounds rather strange, haha! I would appreciate some guidance on how to phrase it better, I'm not quite sure that greater makes sense as I'm not dealing with the length of a string, or a number itself.

Many Thanks!
(Please feel free to move it to the CS forum if you want, I won't be offended!)

Is This A Good Question/Topic? 0
  • +

Replies To: Binary Search Tree with Strings

#2 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 13962
  • View blog
  • Posts: 55,726
  • Joined: 12-June 08

Re: Binary Search Tree with Strings

Posted 29 November 2017 - 03:33 PM

Well.. how _ARE_ you arranging your strings in your tree? What's the comparison?
Was This Post Helpful? 0
  • +
  • -

#3 chloeCodes  Icon User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 178
  • Joined: 05-January 17

Re: Binary Search Tree with Strings

Posted 29 November 2017 - 03:33 PM

I mentioned that I'm using the compareTo()??
Was This Post Helpful? 0
  • +
  • -

#4 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 13962
  • View blog
  • Posts: 55,726
  • Joined: 12-June 08

Re: Binary Search Tree with Strings

Posted 29 November 2017 - 03:36 PM

Mkay.. so what is 'lexicographical ordering'? It's like sorting in a dictionary.. so.. 'alphabetical' or 'dictionary order' would be sufficient.
Was This Post Helpful? 1
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12278
  • View blog
  • Posts: 45,364
  • Joined: 27-December 08

Re: Binary Search Tree with Strings

Posted 30 November 2017 - 10:05 AM

The docs are always a good place to look.

From the Java docs for the String compareTo() method:

Quote

public int compareTo(String anotherString)

Compares two strings lexicographically. The comparison is based on the Unicode value of each character in the strings. The character sequence represented by this String object is compared lexicographically to the character sequence represented by the argument string. The result is a negative integer if this String object lexicographically precedes the argument string. The result is a positive integer if this String object lexicographically follows the argument string. The result is zero if the strings are equal; compareTo returns 0 exactly when the equals(Object) method would return true.

This is the definition of lexicographic ordering. If two strings are different, then either they have different characters at some index that is a valid index for both strings, or their lengths are different, or both. If they have different characters at one or more index positions, let k be the smallest such index; then the string whose character at position k has the smaller value, as determined by using the < operator, lexicographically precedes the other string. In this case, compareTo returns the difference of the two character values at position k in the two string -- that is, the value:

this.charAt(k)-anotherString.charAt(k)


If there is no index position at which they differ, then the shorter string lexicographically precedes the longer string. In this case, compareTo returns the difference of the lengths of the strings -- that is, the value:

this.length()-anotherString.length()


Specified by:
compareTo in interface Comparable<String>
Parameters:
anotherString - the String to be compared.
Returns:
the value 0 if the argument string is equal to this string; a value less than 0 if this string is lexicographically less than the string argument; and a value greater than 0 if this string is lexicographically greater than the string argument.

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1