title: c++ - overload [] operator for Red-Black Tree
body: <p>I'm trying to overload [] for red-black tree. Each node contains four elements: key, gender, height and weight. "key" value will be randomly assigned and should be unique, so I want to overload [] by traversing each node to see if the "key" value already exists. However, it worked only when there was just one node. Here's the code:</p>
  
  <pre><code>#include&lt;iostream&gt;
  #include&lt;string&gt;
  using namespace std;
  
  enum COLOR { RED, BLACK };
  
  class Node
  {
      public:
          Node(int key, string gender, int height, int weight, const COLOR &amp; color = RED)
              :pLeft(NULL), pRight(NULL), pParent(NULL), key(key), gender(gender), height(height), weight(weight), color(color)
          {}
          ~Node();
  
          string getGender();
          int getHeight();
          int getWeight();
  
          Node* pLeft;
          Node* pRight;
          Node* pParent;
          int key;
          string gender;
          int height;
          int weight;
          COLOR color;
  };
  
  class RBTree
  {
      public:
          RBTree() :pRoot(NULL) {}
  
          Node &amp;operator[](int key);
          bool insert(int key, string gender, int height, int weight);
          void RotateL(Node* parent);
          void RotateR(Node* parent);
          void InOrder();
          void InOrder(Node* pRoot);
          Node* searchTree(Node* pRoot, int key);
          bool CheckRBTree();
          bool CheckRBTree(Node* pRoot,int counter,int k);
  
      private:
          Node* pRoot;
  };
  
  string Node::getGender()
  {
      return gender;
  }
  
  int Node::getHeight()
  {
      return height;
  }
  
  int Node::getWeight()
  {
      return weight;
  }
  
  Node &amp;RBTree::operator[](int key)
  {
      Node* ptr = searchTree(pRoot, key);
      return *ptr;
  }
  
  bool RBTree::insert(int key, string gender, int height, int weight)
  {
      // create root
      if (pRoot == NULL)
      {
          pRoot = new Node(key, gender, height, weight);
          pRoot-&gt;color = BLACK;
          return true;
      }
  
      // find loc to insert
      Node* pCur = pRoot;
      Node* parent = NULL;
      while (pCur)
      {
          if (key &lt; pCur-&gt;key)
          {
              parent = pCur;
              pCur = pCur-&gt;pLeft;
          }
          else if (key &gt; pCur-&gt;key)
          {
              parent = pCur;
              pCur = pCur-&gt;pRight;
          }
          else
              return false;
      }
  
      // insert
      pCur = new Node(key, gender, height, weight);
      if (key &lt; parent-&gt;key)
          parent-&gt;pLeft = pCur;
      else
          parent-&gt;pRight = pCur;
  
      pCur-&gt;pParent = parent;
  
      // discuss 3 cases
      while (pRoot != pCur&amp;&amp;pCur-&gt;pParent-&gt;color == RED)
      {
          Node* gf = parent-&gt;pParent;
  
          if (gf-&gt;pLeft == parent)
          {
              Node* uncle = gf-&gt;pRight;
              if (uncle&amp;&amp;uncle-&gt;color == RED)
              {
                  parent-&gt;color = BLACK;
                  uncle-&gt;color = BLACK;
                  gf-&gt;color = RED;
  
                  pCur = gf;
                  parent = pCur-&gt;pParent;
              }
              else // turn case 3 into case 2
              {
                  if (parent-&gt;pRight == pCur)
                  {
                      RotateL(parent);
                      std::swap(parent, pCur);
                  }
  
                  gf-&gt;color = RED;
                  parent-&gt;color = BLACK;
                  RotateR(gf);
              }
          }
          else
          {
              Node*uncle = gf-&gt;pLeft;
              if (uncle &amp;&amp; uncle-&gt;color == RED)  //case 1
              {
                  parent-&gt;color = BLACK;
                  uncle-&gt;color = BLACK;
                  gf-&gt;color = RED;
  
                  pCur = gf;
                  parent = pCur-&gt;pParent;
              }
              else // turn case 3 into case 2
              {
                  if (parent-&gt;pLeft == pCur)
                  {
                      RotateR(parent);
                      std::swap(parent, pCur);
                  }
  
                  gf-&gt;color = RED;
                  parent-&gt;color = BLACK;
                  RotateL(gf);
              }
          }
      }
  
      pRoot-&gt;color = BLACK;
      return true;
  }
  
  // rotate left 
  void RBTree::RotateL(Node* parent)
  {
      Node* subR = parent-&gt;pRight;
      Node* subRL = subR-&gt;pLeft;
  
      parent-&gt;pRight = subRL;
      if (subRL)
          subRL-&gt;pParent = parent;
  
      subR-&gt;pLeft = parent;
      Node* gparent = parent-&gt;pParent; 
      parent-&gt;pParent = subR;
      subR-&gt;pParent = gparent;
  
      if (gparent == NULL)
          pRoot = subR;
      else if (gparent-&gt;pLeft == parent)
          gparent-&gt;pLeft = subR;
      else
          gparent-&gt;pRight = subR;
  
  }
  
  void RBTree::RotateR(Node* parent)
  {
      Node* subL = parent-&gt;pLeft;
      Node* subLR = subL-&gt;pRight;
  
      parent-&gt;pLeft = subLR;
      if (subLR)
          subLR-&gt;pParent = parent;
  
      subL-&gt;pRight = parent;
      Node* gparent = parent-&gt;pParent;
      parent-&gt;pParent = subL;
      subL-&gt;pParent = gparent;
  
      if (gparent == NULL)
          pRoot = subL;
      else if (gparent-&gt;pLeft == parent)
          gparent-&gt;pLeft = subL;
      else
          gparent-&gt;pRight = subL;
  }
  
  void RBTree::InOrder()
  {
      cout &lt;&lt; "InOrder:  ";
      InOrder(pRoot);
      cout &lt;&lt; endl;
  }
  
  void RBTree::InOrder(Node* pRoot)
  {
      if (pRoot)
      {
          InOrder(pRoot-&gt;pLeft);
          cout &lt;&lt; pRoot-&gt;key &lt;&lt; "  ";
          InOrder(pRoot-&gt;pRight);
      }
  }
  
  Node* RBTree::searchTree(Node* pRoot, int key)
  {
      if(pRoot-&gt;key == key)
          return pRoot;
  
      if(pRoot)
      {
          cout &lt;&lt; "current node is " &lt;&lt; pRoot-&gt;key &lt;&lt; endl;
          searchTree(pRoot-&gt;pLeft, key);
          searchTree(pRoot-&gt;pRight, key);
      }
      return NULL;
  }
  
  bool RBTree::CheckRBTree()
  {
      if (pRoot == NULL)
          return true;
      if (pRoot-&gt;color == RED)
          return false;
      int blackcount = 0;
  
      Node* pCur = pRoot;
      while (pCur)
      {
          if (pCur-&gt;color == BLACK)
              blackcount++;
          pCur = pCur-&gt;pLeft;
      }
  
      return CheckRBTree(pRoot, blackcount, 0);
  }
  
  bool RBTree::CheckRBTree(Node* pRoot, int counter, int k)
  {
      if (pRoot == NULL)
          return true;
      if (pRoot-&gt;color == BLACK)
          k++;
  
      Node* parent = pRoot-&gt;pParent;
      if (parent &amp;&amp; parent-&gt;color == RED &amp;&amp; pRoot-&gt;color == RED)
          return false;
  
      if (pRoot == NULL)
      {
          if (k != counter)
              return false;
      }
  
      return CheckRBTree(pRoot-&gt;pLeft, counter, k)
          &amp;&amp; CheckRBTree(pRoot-&gt;pRight, counter, k);
  }
  
  int main()
  {
      int a[] = { 10, 7, 8, 15, 5, 6, 11, 13, 12 };
  
      RBTree t;
      for (int index = 0; index &lt; sizeof(a) / sizeof(a[0]); index++)
      {
          cout &lt;&lt; a[index] &lt;&lt; "  ";
          t.insert(a[index], "male", 12, 3);
      }
      cout &lt;&lt; endl;
      cout &lt;&lt; t[7].getGender() &lt;&lt; endl;
  
      return 0;
  }
  </code></pre>
  
  <p>Anyone knows how to fix this? Thanks in advance.</p>