Re: [Dev-C++] binary tree search + need to find char*

[Per W. <pw...@ia...>]

A recursive descent of a binary tree is O(log n) efficient if the tree is
balanced. That is as fast as you can locate data in a tree. Note that the
tree recursion is ONLY (!) efficient if the tree is balanced, i.e. if all
branches of the tree are of same height or same height-1. The worst case
is a naive implementation which - when the inserted entries are already
sorted - makes a long chain, where one branch of the tree is empty and the
other branch forms a long deep list:

   alpha
(nil)   bravo
     (nil)  charlie
            (nil)  delta

If the tree is so big that it doesn't fit in memory, then you can change
from a binary tree to a btree or a red-black-tree, where the tree branches
out wider on each level. This increases the processing time of each node,
but reduces number of nodes to visit, thereby reducing number of disk
accesses. A typical btree or rb-tree has 16-64 branches on each node.

Even faster lookups are possible if you change to a hash table. Then you
can locate the data in constant time. Keep a large array of lists. For the
search parameter, evaluate a randomizing function (called a hash function)
and use this value modulo number of positions in the array to decide which
list to search. If you have 10^4 entries and a 10^3 long array, each list
is on average 10 entries long. The disadvantage with the hash table is
that the entries are not sorted, so you can't locate the next
bigger/smaller entry without scanning through all entries. Also, it
requires that the hash function generates good random distribution of the
entries, to avoid a lot of hash buckets to be empty, while some are
seriously overloaded.

/Per W

On 9 Jul 2003, Peter Mead wrote:

> Hello,
> I am still learning C++ and I am not sure how to do this.
> I am writing a dictionary for use with secondary students. The words,
> descriptions and a unique code get read in from a binary file on disk
> and stored in individual nodes of a binary search tree according to the
> code in each entry of the binary file on disk.
> i can retrieve a word and description at runtime by using the code as
> given by the user however, i need to be able to search the tree
> structure for the word as given by the user. i can find the word by
> testing recursively, but i there is a more efficient way to do this.
>
> here is the search for the code:
> ////////////////////////////////////////////////////
>  DicTreeNode* DicBinaryTree::idBTreeSearch(DicTreeNode* nodePtr, long
> dicId) {
>  if (nodePtr != 0) {
>  if (dicId < nodePtr->id){
>  this->idBTreeSearch(nodePtr->leftChild,dicId);
>  }
>  else if (dicId > nodePtr->id) {
>  this->idBTreeSearch(nodePtr->rightChild,dicId);
>  }
>  else {
>  rtnNodePtr = nodePtr;
>  }
>  return rtnNodePtr;
>  }
>  else {
>  return nodePtr = 0;
>  }
> }
> ////////////////////////////////////////////////////
> the above code works fine with a long as the id for the search...
> the code below works but is not a good way of doing the search...
> ////////////////////////////////////////////////////
>  DicTreeNode* DicBinaryTree::wordBTreeSearch(DicTreeNode* nodePtr, char*
> dicWord ){
>  if (nodePtr != 0) { // this method of finding the word is not
> efficient...
>  this->wordBTreeSearch(nodePtr->leftChild,dicWord);
>  this->wordBTreeSearch(nodePtr->rightChild,dicWord);
>  if (!strcmp(nodePtr->word,dicWord)) {
>  this->rtnNodePtr = nodePtr;
>  }
>  return this->rtnNodePtr;
>  }
>  else{
>  return nodePtr = 0;
>  }
> }
> ////////////////////////////////////////////////////
> any ideas??
> TIA
> Peter Mead.
>
>
>
>
> -------------------------------------------------------
> This SF.Net email sponsored by: Parasoft
> Error proof Web apps, automate testing & more.
> Download & eval WebKing and get a free book.
> www.parasoft.com/bulletproofapps
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www23.brinkster.com/noicys/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>