Sample of a Binary Tree Search

Environment: All C++ environments

The purpose of this article is show a method for binary tree searching with large numbers of strings.

I wrote a function that works with a list of pointers to alphabetically ordered strings. It can be a list of people, a dictionary, and so forth.

The function takes four arguments. The first is a pointer to the string we want to search. The next is a pointer to the first char pointer of some big list of char pointers. The next argument is the low subindex of the char pointers array and the last argument is the high subindex of the char pointers array.

The last two arguments allow the users to specify a subset of the char pointer's array to search the desired string. The function supposes that the array of char pointers is alphabetically ordered; this means that the first char pointer points to some string, the next char pointer points to some major string, and so on, from minor alphabetically to major alphabetically.

#define MAX_SRCH_LEVELS 32

/* BinaryTreeSearchEx
 *      Searches a character string in a list of alphabetic strings
 *      Searching is made within the limits of FirsItem to LastItem
 *      using a binary tree searching method.
 *
 * Arguments:
 *      Desired     a pointer to the string we want to find
 *      PtrList     a pointer to the first char pointer of the list
 *      FirstItem   the low subindex limit of PtrList array of
 *                  pointers
 *      LastItem    the high subindex limit of PtrList array of
 *                  pointers
 *
 *      The function supposes that pointers in PtrList point to
 *          alphabetically ordered strings
 *      FirstItem and LastItem allow the user to find in a subset
 *          of PtrList array of pointers
 *      The lowest index value is 0; that is, the first pointer
 *          of PtrList
 *      The highest index value is (4 294 967 294 - 1)
 *
 * Methods:
 *      Searching by binary tree
 *      Maximum number of parsings allowed are 32
 *
 * Returns:
 *      When found returns index value
 *      When not found returns 0xFFFFFFFF
 */
DWORD BinaryTreeSearchEx(char *Desired, char **PtrList,
                         DWORD FirstItem, DWORD LastItem)
{
  DWORD LowIndex = FirstItem;
  DWORD HighIndex = LastItem;
  DWORD SrchIndex;
  DWORD Amplitude;
  int cmpValue;
  int count;

  // binary tree search loop
  for (count = 0; count < MAX_SRCH_LEVELS; count++)
  {
    // Calculates the amplitude of this search level
    Amplitude = (HighIndex - LowIndex) + 1;
    if (Amplitude > 0)
    {
      SrchIndex = LowIndex + (Amplitude / 2);
    }
    else
    {
      SrchIndex = LowIndex;
    }

    // equal in length and all characters
    if ((cmpValue = strcmp(Desired, PtrList[SrchIndex])) == 0)
                           return (SrchIndex);

    // desired string is equal to the beginning of source string
    if (strstr(PtrList[SrchIndex], Desired) == PtrList[SrchIndex])
                           return (SrchIndex);

    // when HighIndex is equal to LowIndex, we must break the loop
    if (HighIndex == LowIndex) break;

    // if minor, set new limits
    if (cmpValue < 0)
    {
      if (SrchIndex > 0)
      {
        HighIndex = SrchIndex - 1;
      }
      else
      {
        HighIndex = 0;
      }
    }

    // if major, set new limits
    if (cmpValue > 0)
    {
      if (SrchIndex < LastItem)
      {
        LowIndex = SrchIndex + 1;
      }
      else
      {
        LowIndex = LastItem;
      }
    }

  // Next search level
  }

  // Function returns without success
  return (0xFFFFFFFF);
}


Comments

  • subindex is not a word

    Posted by Legacy on 09/18/2003 12:00am

    Originally posted by: karl anliot

    subindex is not a word. I find this example valuable.

    Reply
  • Why?

    Posted by Legacy on 12/04/2002 12:00am

    Originally posted by: Norm

    Ok, so the STL has a perfectly good binary search in <algorithm> called binary_search, but even if you don't want to use the STL there is still the ANSI standard bsearch!

    template<class FwdIt, class T>
    bool binary_search(FwdIt first, FwdIt last, const T& val);
    template<class FwdIt, class T, class Pred>
    bool binary_search(FwdIt first, FwdIt last, const T& val, Pred pr);

    void *bsearch( const void *key, const void *base, size_t num, size_t width, int ( __cdecl *compare ) ( const void *elem1, const void *elem2 ) );


    Norm

    Reply
  • Ternary trees

    Posted by Legacy on 12/03/2002 12:00am

    Originally posted by: Rob Pieke

    There's an interesting article I read a while back on ternary trees, which have some interesting benefits over binary trees when it comes to dealing with strings.

    http://www.ddj.com/documents/s=921/ddj9804a/9804a.htm

    Reply
Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Agile methodologies give development and test teams the ability to build software at a faster rate than ever before. Combining DevOps with hybrid cloud architectures give teams not just the principles, but also the technology necessary to achieve their goals. By combining hybrid cloud and DevOps: IT departments maintain control, visibility, and security Dev/test teams remain agile and collaborative Organizational barriers are broken down Innovation and automation can thrive Download this white paper to …

  • On-demand Event Event Date: September 10, 2014 Modern mobile applications connect systems-of-engagement (mobile apps) with systems-of-record (traditional IT) to deliver new and innovative business value. But the lifecycle for development of mobile apps is also new and different. Emerging trends in mobile development call for faster delivery of incremental features, coupled with feedback from the users of the app "in the wild." This loop of continuous delivery and continuous feedback is how the best mobile …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds