CODEWITHSUNDEEP
javabinary-treebinary-search-tree
TeddyG
TeddyG

Reputation: 559

Binary Search Tree of Strings

I had a question of exactly how a binary search tree of strings works. I know and have implemented binary search trees of integers by checking if the new data <= parent data then by branching left if its less or right if its greater. However I am a little confused on how to implement this with nodes of strings.

With the integers or characters I can just insert in an array into my insert method of the tree i programmed and it builds the tree nodes correctly. My question is how you would work this with an array of strings. How would you get the strings to branch off correctly in the tree? For example if I had an array of questions how would I be able to branch the BST correctly so I would eventually get to the correct answer.

For example look at the following trivial tree example. 

                                        land animal?            
                   have tentacles?------------^-------------indoor animal
          have claws?-----^----jellyfish    live in jungle?----^----does it bark?      
eat plankton?----^----lobster             bear----^----lion        cat----^----dog
shark----^----whale

How would you populate a tree such as this so that nodes populate where how you want them. I am trying to make a BST for trouble shooting and i am confused how to populate the nodes of strings so they appear in the correct positions. Do you need to hard code the nodes?

Upvotes: 1

Views: 1569

Answers (1)

user166390
user166390

Reputation:

Update 2, to build a binary decision tree:

A binary decision tree can be thought of as a bunch of questions that yield boolean responses about facets of leaf nodes - the facet either exists / holds true or it does not. That is, for every descendent of a particular node/edge we must be able to say "this question/answer holds" (answers can be "true" or "false"). For instance, a bark is a facet of a (normal) dog, but tentacles are not a facet of a Whale. In the presented tree, the false edge always leads to the left subtree: this is a convention to avoid labeling each edge with true/false or Y/N.

The tree can only be built from existing/external knowledge that allows one to answer each question for every animal.

Here is a rough algorithm can be used to build such a tree:

  1. Start with a set of possible animals, call this A, and a set of questions, call this Q.
  2. Pick a question, q, from Q for which count(True(q, a in A)) is closest to that of count(False(q, a in A)) - if the resulting tree is a balanced binary tree these counts will always be equal for the best question to ask.
  3. Remove q from Q and use it as the question to ask for the current node. Put all False(q,a) into the set of animals (A') available to the left child node and put all True(q,a) into the set of animals (A'') available to the right child node.
  4. Following each edge/branch (false=left, true=right), pick a suitable question from the remaining Q and repeat (using A' or A'' for A, as appropriate).

(Of course, there are many more complete/detailed/accurate resources found online as course material or whitepapers. Not to mention a suitable selection of books at most college campuses ..)

Update, for a [binary] decision tree:

In this particular case (which is clear with the added diagram) the graph is based on the "yes" or "no" response for the question which represent the edges between the nodes. That is, the tree is not not built using an ordering of the string values themselves. In this case it might make sense to always have the left branch "false" and the right branch "true" although each node could have more edges/children if non-binary responses are allowed.

The decision tree must be "trained" (google search). That is, the graph must be built initially based on the questions/responses which is unlike a BST that is based merely on ordering between nodes. The initial graph building cannot be done from merely an array of questions as the edges do not follow an intrinsic ordering.

Initial response, for a binary search tree:

The same way it does for integers: the algorithm does not change.

Consider a function, compareTo(a,b) that will return -1, 0 or 1 for a < b, a == b, and a > b, respectively.

Then consider that the type of neither a nor b matter (as long as they are the same) when implementing a function with this contract if such a type supports ordering: it will be "raw" for integers and use the host language's corresponding string comparison for string types.

Upvotes: 1

Related Questions