基于红黑树的一个线段树实现

#include "interval_tree.h" #include <stdio.h> #include <math.h> #include <stdlib.h> #define EPSILON 1e-12 // If the symbol CHECK_INTERVAL_TREE_ASSUMPTIONS is defined then the // code does a lot of extra checking to make sure certain assumptions // are satisfied. This only needs to be done if you suspect bugs are // present or if you make significant changes and want to make sure // your changes didn't mess anything up. // #define CHECK_INTERVAL_TREE_ASSUMPTIONS 1 const Real MIN_KEY=-MAX_KEY; // define a function to find the maximum of two objects. #define ITMax(a, b) ( (a > b) ? a : b ) inline void Assert(int assertion, char* error) { if(!assertion) { printf("Assertion Failed: %s\n",error); exit(1); } } IntervalTreeNode::IntervalTreeNode(){} IntervalTreeNode::IntervalTreeNode(Interval * newInterval) : storedInterval (newInterval) , key(newInterval->GetLowPoint()), high(newInterval->GetHighPoint()) , maxHigh(high) {} IntervalTreeNode::~IntervalTreeNode(){} Interval::Interval(){} Interval::~Interval(){} void Interval::Print() const {} IntervalTree::IntervalTree() { nil = new IntervalTreeNode; nil->left = nil->right = nil->parent = nil; nil->red = 0; nil->key = nil->high = nil->maxHigh = MIN_KEY; nil->storedInterval = NULL; root = new IntervalTreeNode; root->parent = root->left = root->right = nil; root->key = root->high = root->maxHigh = MAX_KEY; root->red=0; root->storedInterval = NULL; /* the following are used for the Enumerate function */ //recursionNodeStackSize = 128; //recursionNodeStack = (it_recursion_node *) // malloc(recursionNodeStackSize*sizeof(it_recursion_node)); //recursionNodeStackTop = 1; //recursionNodeStack[0].start_node = NULL; } /***********************************************************************/ /* FUNCTION: LeftRotate */ /**/ /* INPUTS: the node to rotate on */ /**/ /* OUTPUT: None */ /**/ /* Modifies Input: this, x */ /**/ /* EFFECTS: Rotates as described in _Introduction_To_Algorithms by */ /* Cormen, Leiserson, Rivest (Chapter 14). Basically this */ /* makes the parent of x be to the left of x, x the parent of */ /* its parent before the rotation and fixes other pointers */ /* accordingly. Also updates the maxHigh fields of x and y */ /* after rotation. */ /***********************************************************************/ void IntervalTree::LeftRotate(IntervalTreeNode* x) { IntervalTreeNode* y; /* I originally wrote this function to use the sentinel for */ /* nil to avoid checking for nil. However this introduces a */ /* very subtle bug because sometimes this function modifies */ /* the parent pointer of nil. This can be a problem if a */ /* function which calls LeftRotate also uses the nil sentinel */ /* and expects the nil sentinel's parent pointer to be unchanged */ /* after calling this function. For example, when DeleteFixUP */ /* calls LeftRotate it expects the parent pointer of nil to be */ /* unchanged. */ /// x y /// / \ / \ /// A y -> x C /// / \ / \ /// B C A B y=x->right; x->right=y->left; if (y->left != nil) y->left->parent=x; /* used to use sentinel here */ /* and do an unconditional assignment instead of testing for nil */ y->parent=x->parent; /* instead of checking if x->parent is the root as in the book, we */ /* count on the root sentinel to implicitly take care of this case */ if( x == x->parent->left) { x->parent->left=y; } else { x->parent->right=y; } y->left=x; x->parent=y; x->maxHigh=ITMax(x->left->maxHigh,ITMax(x->right->maxHigh,x->high)); y->maxHigh=ITMax(x->maxHigh,ITMax(y->right->maxHigh,y->high)); #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS CheckAssumptions(); #elif defined(DEBUG_ASSERT) Assert(!nil->red,"nil not red in ITLeftRotate"); Assert((nil->maxHigh=MIN_KEY), "nil->maxHigh != MIN_KEY in ITLeftRotate"); #endif } /***********************************************************************/ /* FUNCTION: RighttRotate */ /**/ /* INPUTS: node to rotate on */ /**/ /* OUTPUT: None */ /**/ /* Modifies Input?: this, y */ /**/ /* EFFECTS: Rotates as described in _Introduction_To_Algorithms by */ /* Cormen, Leiserson, Rivest (Chapter 14). Basically this */ /* makes the parent of x be to the left of x, x the parent of */ /* its parent before the rotation and fixes other pointers */ /* accordingly. Also updates the maxHigh fields of x and y */ /* after rotation. */ /***********************************************************************/ void IntervalTree::RightRotate(IntervalTreeNode* y) { IntervalTreeNode* x; /* I originally wrote this function to use the sentinel for */ /* nil to avoid checking for nil. However this introduces a */ /* very subtle bug because sometimes this function modifies */ /* the parent pointer of nil. This can be a problem if a */ /* function which calls LeftRotate also uses the nil sentinel */ /* and expects the nil sentinel's parent pointer to be unchanged */ /* after calling this function. For example, when DeleteFixUP */ /* calls LeftRotate it expects the parent pointer of nil to be */ /* unchanged. */ /// y x /// / \ / \ /// x C --> A y /// / \ / \ /// A B B C x=y->left; y->left=x->right; if (nil != x->right) x->right->parent=y; /*used to use sentinel here */ /* and do an unconditional assignment instead of testing for nil */ /* instead of checking if x->parent is the root as in the book, we */ /* count on the root sentinel to implicitly take care of this case */ x->parent=y->parent; if( y == y->parent->left) { y->parent->left=x; } else { y->parent->right=x; } x->right=y; y->parent=x; y->maxHigh=ITMax(y->left->maxHigh,ITMax(y->right->maxHigh,y->high)); x->maxHigh=ITMax(x->left->maxHigh,ITMax(y->maxHigh,x->high)); #ifdef CHECK_INTERVAL_TREE_ASSUMPTIONS CheckAssumptions(); #elif defined(DEBUG_ASSERT) Assert(!nil->red,"nil not red in ITRightRotate"); Assert((nil->maxHigh=MIN_KEY), "nil->maxHigh != MIN_KEY in ITRightRotate"); #endif } /***********************************************************************/ /* FUNCTION: TreeInsertHelp */ /**/ /* INPUTS: z is the node to insert */ /**/ /* OUTPUT: none */ /**/ /* Modifies Input: this, z */ /**/ /* EFFECTS: Inserts z into the tree as if it were a regular binary tree */ /* using the algorithm described in _Introduction_To_Algorithms_ */ /* by Cormen et al. This funciton is only intended to be called */ /* by the InsertTree function and not by the user */ /***********************************************************************/ void IntervalTree::TreeInsertHelp(IntervalTreeNode* z) { /* This function should only be called by InsertITTree (see above) */ IntervalTreeNode* x; IntervalTreeNode* y; z->left=z->right=nil; y=root; x=root->left; while( x != nil) { y=x; if ( x->key > z->key) { x=x->left; } else { /* x->key <= z->key */ x=x->right; } } z->parent=y; if ( (y == root) || (y->key > z->key) ) { y->left=z; } else { y->right=z; } #if defined(DEBUG_ASSERT) Assert(!nil->red,"nil not red in ITTreeInsertHelp"); Assert((nil->maxHigh=MIN_KEY), "nil->maxHigh != MIN_KEY in ITTreeInsertHelp"); #endif } /***********************************************************************/ /* FUNCTION: FixUpMaxHigh */ /**/ /* INPUTS: x is the node to start from*/ /**/ /* OUTPUT: none */ /**/ /* Modifies Input: this */ /**/ /* EFFECTS: Travels up to the root fixing the maxHigh fields after */ /* an insertion or deletion */ /***********************************************************************/ void IntervalTre