// RedBlackTree.h 
// does not allow duplicate items
// wdg 2008
#include "RBNode.h"
#include "BinarySearchTree.h"

class RedBlackTree : public BinarySearchTree
{ 
  public:
    RedBlackTree();
    void insertItem(ItemType it);
  
  private:
    void leftRotate(RBNode *x);   
    void rightRotate(RBNode *x);
    RBNode *grand(RBNode *v);
    RBNode *uncle(RBNode *v);
    bool isLeftChild(BSTNode *v);
}; // end of class