Binary Search Tree Help Needed

[tsunami]

hi all;

I have an array and want to insert all the elements from this array to
a binary search tree.That array is an object of the class of a
stringtype which includes overloaded "< > = ==" functions and every
other thing it needs.

void InsertElementFromArray(StringType Array,int first element,int
last element);

that member function takes the array,first element of the array,last
element of the array as parameters.Array is sorted array.this
application is going to be used as spellchecker.if you supply any info
I will be glad.

 

[Mark P]

hi all;

I have an array and want to insert all the elements from this array to
a binary search tree.That array is an object of the class of a
stringtype which includes overloaded "< > = ==" functions and every
other thing it needs.

void InsertElementFromArray(StringType Array,int first element,int
last element);

that member function takes the array,first element of the array,last
element of the array as parameters.Array is sorted array.this
application is going to be used as spellchecker.if you supply any info
I will be glad.

I'm not entirely clear what you're asking for. You can use std::set (or
any of its cousins map, multiset, or multimap) as a sorted container
which supports O(log n) searches, inserts, removals, and more.
Typically these are implemented with binary search trees (every
implementation I've seen uses red-black trees though this is not
mandatory).

Of course if you already have a sorted array and don't intend to add or
remove elements from it, it's pretty easy to perform O(log n) searches
on that directly.

But if you're making a spell-checker a BST may not be ideal. If you
only want to check if a word is in a fixed dictionary then a hash table
is probably better. If you need to suggest lexically similar words then
a hash table is no good, but a simple sorted structure probably won't
perform very well at this task either.

 

[osmium]

I have an array and want to insert all the elements from this array to
a binary search tree.That array is an object of the class of a
stringtype which includes overloaded "< > = ==" functions and every
other thing it needs.

void InsertElementFromArray(StringType Array,int first element,int
last element);

that member function takes the array,first element of the array,last
element of the array as parameters.Array is sorted array.this
application is going to be used as spellchecker.if you supply any info
I will be glad.

The only problem I see is that the array is sorted; putting a sorted array
into a tree will give the worst possible tree. I assume you are not
supposed to change the input array. If the array contains n elements I
would create an auxiliary array with elements numbered 0..n-1. Randomize
this array ( see the shuffle algorithm as used in a card game) and use the
auxiliary array to access the original array. The tree will see the
elements arriving in random order.

 

[Mark P]

:




The only problem I see is that the array is sorted; putting a sorted array
into a tree will give the worst possible tree. I assume you are not
supposed to change the input array. If the array contains n elements I
would create an auxiliary array with elements numbered 0..n-1. Randomize
this array ( see the shuffle algorithm as used in a card game) and use the
auxiliary array to access the original array. The tree will see the
elements arriving in random order.

Why throw away the sort information and waste time randomizing when you
can build a balanced binary tree very easily from a sorted array? There
are a variety of ways to do this, but they all follow the general
strategy of breaking the list in half and recursively building a tree
from each half.

Really this isn't even necessary, except perhaps for conceptual
understanding, since searching in a sorted array is already as easy as
searching in a balanced binary tree.