Binary Search Trees Predesessor & Successor Problems

This is a discussion on Binary Search Trees Predesessor & Successor Problems within the C++ Programming forums, part of the General Programming Boards category; I am coding an implmentation of a standard BST. This is my first implementation I am having problems with the ...

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    6

    Binary Search Trees Predesessor & Successor Problems

    I am coding an implmentation of a standard BST. This is my first implementation I am having problems with the predesessor and successor parts. Maybe someone could lend me some insight.

    I have all the find post, in, pre -order traversals i need the succ & pred & delete. I need the succ for the delete and i'm burned put on this program. I need help.
    Here is what i am trying to accomplish.
    pred, moves the pointer to the predecessor of the current node, prints the value that proceeds the string or the line "No Previous"

    succ, moves the pointer to the successor of the current node, prints the value that follows the string or the line "No Next"

    Code:
    //MY GLOBAL STRUCTS FOR THE NODES
    
    struct Wrd {
           int wordcounter;					// counter
           string theword;					// the actual word
    };
    
    struct TreeNode {
           Wrd item;         			        // the data struct
           TreeNode *parent;				// pointer to the parent
           TreeNode *left;   				   // pointer to left subtree
           TreeNode *right;  				  // pointer to right subtree
    };
    
    TreeNode *root = NULL;					// root of the tree & init to NULL
    
    TreeNode* succ(TreeNode *T){
             TreeNode *x, *y;
    
             if (T == NULL){
                return T;
             }
             if (T->right != NULL){
                 return min(T->right);
             }
             y = T->parent;
             while (y != NULL && x == y->right){
                    x = y;
                    y = y->parent;
             }
    return y;
    }
    
    //THE CALL
     succ(root);

  2. #2
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    Successor: Once to the right, and then as far to the left as you can go without hitting null. Pseudocode:

    Code:
    Node* find_successor(Node* root)
    {
        if (!root) return NULL;
    
        root = root->right;
        if (!root) return NULL;
     
        while (root->left) {
            root = root->left;
        }
        return root;
    }
    Predecessor: root->left if not null, otherwise parent of root.
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Successor: Once to the right, and then as far to the left as you can go without hitting null.
    What's the successor of 4 in the following tree using that definition? If you're only finding the successor in a downward path (such as insertion), then yes, that's correct. But if you want a general successor function you also have to consider upward movement too.
    Code:
            5
    
          /   \
    
        2       9
    
      /   \
    
    1       4
    Here's a function that finds the successor using parent pointers. A predecessor function just changes right to left and left to right:
    Code:
    iNode *succ ( Node *node )
    {
      if ( node->right != NULL ) {
        /* Go down */
        node = node->right;
    
        while ( node->left != NULL )
          node = node->left;
      }
      else {
        /* Go up */
        for ( ; ; ) {
          if ( node->parent == NULL || node == node->parent->left ) {
            node = node->parent;
            break;
          }
    
          node = node->parent;
        }
      }
    
      return node;
    }
    >Predecessor: root->left if not null, otherwise parent of root.
    The predecessor is the exact mirror of the successor in a basic tree, so your description is missing a few steps.
    My best code is written with the delete key.

  4. #4
    Registered User
    Join Date
    Nov 2005
    Posts
    6

    Angry

    Great Thanks!! I got both of those working perfectly.
    I have few more questions though involving pointers. I'm pulling my hair out!

    I need to accomplish the following
    > first, moves the pointer to the minimum value in the tree or NULL.
    > last, moves the pointer to the maximum value in the tree or NULL.
    > root, moves the pointer to point to the root of the tree
    > left, moves the pointer to point to the left child of the current node or to NULL.
    > right, moves the pointer to point to the right child of the current node or to NULL.

    I am confused by how i determine the current node
    most of my functions follow the following format for example my function that shows the max of the tree.
    Code:
    TreeNode* max(TreeNode *T){//WORKS!!
              Wrd e;
    
              if (T == NULL){
                  cout << "Tree Empty" << endl;
                  return T;
              }
              while (T->right != NULL){
                     T = T->right;
              }
              e.theword = T->item.theword;
              e.wordcounter = T->item.wordcounter;
              cout << e.theword << ":" << e.wordcounter << endl;
    return T;
    }
    which is called from my main like so
    Code:
                    max(root);
    if my main passes nothing how do i track the current node?
    do i need another pointer trailing it like a linked list.
    dosen't that break the entire point of trees?

    Can someone explain how i find the current node and manipulate it? Any help would be greatly appreciated!!

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >I am confused by how i determine the current node
    The current node is the one you pass to the function:
    Code:
    TreeNode *left ( TreeNode *curr )
    {
      return curr->left;
    }
    My best code is written with the delete key.

  6. #6
    Registered User
    Join Date
    Nov 2005
    Posts
    6
    I passed in the root. So am i changing the root? Do i need to keep track of the root?

  7. #7
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >So am i changing the root?
    Only if you assign the return value to your root pointer:
    Code:
    root = max ( root ); // Changes root
    p = max ( root ); // Doesn't change root
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Performance issue!
    By maven in forum C Programming
    Replies: 42
    Last Post: 03-23-2009, 12:57 PM
  2. Binary Trees
    By wvu2005 in forum C Programming
    Replies: 7
    Last Post: 10-15-2005, 05:59 PM
  3. binary search tree
    By unregistered in forum C++ Programming
    Replies: 4
    Last Post: 12-11-2001, 11:42 AM
  4. Ornery binary search algorithm
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 11-17-2001, 03:32 PM
  5. Newbie questions regarding binary search trees
    By Ham in forum C++ Programming
    Replies: 1
    Last Post: 11-04-2001, 07:48 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21