57 #include <stk_util/util/config_eastl.h> 58 #include <stk_util/util/red_black_tree_eastl.h> 66 rbtree_node_base*
RBTreeRotateLeft(rbtree_node_base* pNode, rbtree_node_base* pNodeRoot);
67 rbtree_node_base*
RBTreeRotateRight(rbtree_node_base* pNode, rbtree_node_base* pNodeRoot);
76 if(pNode->mpNodeRight)
78 pNode = pNode->mpNodeRight;
80 while(pNode->mpNodeLeft)
81 pNode = pNode->mpNodeLeft;
87 while(pNode == pNodeTemp->mpNodeRight)
90 pNodeTemp = pNodeTemp->mpNodeParent;
93 if(pNode->mpNodeRight != pNodeTemp)
107 if((pNode->mpNodeParent->mpNodeParent == pNode) && (pNode->mColor == kRBTreeColorRed))
108 return pNode->mpNodeRight;
109 else if(pNode->mpNodeLeft)
113 while(pNodeTemp->mpNodeRight)
114 pNodeTemp = pNodeTemp->mpNodeRight;
121 while(pNode == pNodeTemp->mpNodeLeft)
124 pNodeTemp = pNodeTemp->mpNodeParent;
142 for(; pNodeBottom; pNodeBottom = pNodeBottom->mpNodeParent)
144 if(pNodeBottom->mColor == kRBTreeColorBlack)
147 if(pNodeBottom == pNodeTop)
163 pNode->mpNodeRight = pNodeTemp->mpNodeLeft;
165 if(pNodeTemp->mpNodeLeft)
166 pNodeTemp->mpNodeLeft->mpNodeParent = pNode;
167 pNodeTemp->mpNodeParent = pNode->mpNodeParent;
169 if(pNode == pNodeRoot)
170 pNodeRoot = pNodeTemp;
171 else if(pNode == pNode->mpNodeParent->mpNodeLeft)
172 pNode->mpNodeParent->mpNodeLeft = pNodeTemp;
174 pNode->mpNodeParent->mpNodeRight = pNodeTemp;
176 pNodeTemp->mpNodeLeft = pNode;
177 pNode->mpNodeParent = pNodeTemp;
192 pNode->mpNodeLeft = pNodeTemp->mpNodeRight;
194 if(pNodeTemp->mpNodeRight)
195 pNodeTemp->mpNodeRight->mpNodeParent = pNode;
196 pNodeTemp->mpNodeParent = pNode->mpNodeParent;
198 if(pNode == pNodeRoot)
199 pNodeRoot = pNodeTemp;
200 else if(pNode == pNode->mpNodeParent->mpNodeRight)
201 pNode->mpNodeParent->mpNodeRight = pNodeTemp;
203 pNode->mpNodeParent->mpNodeLeft = pNodeTemp;
205 pNodeTemp->mpNodeRight = pNode;
206 pNode->mpNodeParent = pNodeTemp;
226 pNode->mpNodeParent = pNodeParent;
227 pNode->mpNodeRight = NULL;
228 pNode->mpNodeLeft = NULL;
229 pNode->mColor = kRBTreeColorRed;
232 if(insertionSide == kRBTreeSideLeft)
234 pNodeParent->mpNodeLeft = pNode;
236 if(pNodeParent == pNodeAnchor)
238 pNodeAnchor->mpNodeParent = pNode;
239 pNodeAnchor->mpNodeRight = pNode;
241 else if(pNodeParent == pNodeAnchor->mpNodeLeft)
242 pNodeAnchor->mpNodeLeft = pNode;
246 pNodeParent->mpNodeRight = pNode;
248 if(pNodeParent == pNodeAnchor->mpNodeRight)
249 pNodeAnchor->mpNodeRight = pNode;
253 while((pNode != pNodeRootRef) && (pNode->mpNodeParent->mColor == kRBTreeColorRed))
255 rbtree_node_base*
const pNodeParentParent = pNode->mpNodeParent->mpNodeParent;
257 if(pNode->mpNodeParent == pNodeParentParent->mpNodeLeft)
261 if(pNodeTemp && (pNodeTemp->mColor == kRBTreeColorRed))
263 pNode->mpNodeParent->mColor = kRBTreeColorBlack;
264 pNodeTemp->mColor = kRBTreeColorBlack;
265 pNodeParentParent->mColor = kRBTreeColorRed;
266 pNode = pNodeParentParent;
270 if(pNode == pNode->mpNodeParent->mpNodeRight)
272 pNode = pNode->mpNodeParent;
276 pNode->mpNodeParent->mColor = kRBTreeColorBlack;
277 pNodeParentParent->mColor = kRBTreeColorRed;
285 if(pNodeTemp && (pNodeTemp->mColor == kRBTreeColorRed))
287 pNode->mpNodeParent->mColor = kRBTreeColorBlack;
288 pNodeTemp->mColor = kRBTreeColorBlack;
289 pNodeParentParent->mColor = kRBTreeColorRed;
290 pNode = pNodeParentParent;
294 if(pNode == pNode->mpNodeParent->mpNodeLeft)
296 pNode = pNode->mpNodeParent;
300 pNode->mpNodeParent->mColor = kRBTreeColorBlack;
301 pNodeParentParent->mColor = kRBTreeColorRed;
307 pNodeRootRef->mColor = kRBTreeColorBlack;
326 if(pNodeSuccessor->mpNodeLeft == NULL)
327 pNodeChild = pNodeSuccessor->mpNodeRight;
328 else if(pNodeSuccessor->mpNodeRight == NULL)
329 pNodeChild = pNodeSuccessor->mpNodeLeft;
333 pNodeSuccessor = pNodeSuccessor->mpNodeRight;
335 while(pNodeSuccessor->mpNodeLeft)
336 pNodeSuccessor = pNodeSuccessor->mpNodeLeft;
338 pNodeChild = pNodeSuccessor->mpNodeRight;
342 if(pNodeSuccessor == pNode)
344 pNodeChildParent = pNodeSuccessor->mpNodeParent;
347 pNodeChild->mpNodeParent = pNodeSuccessor->mpNodeParent;
349 if(pNode == pNodeRootRef)
350 pNodeRootRef = pNodeChild;
353 if(pNode == pNode->mpNodeParent->mpNodeLeft)
354 pNode->mpNodeParent->mpNodeLeft = pNodeChild;
356 pNode->mpNodeParent->mpNodeRight = pNodeChild;
360 if(pNode == pNodeLeftmostRef)
364 if(pNode->mpNodeRight)
365 pNodeLeftmostRef = RBTreeGetMinChild(pNodeChild);
367 pNodeLeftmostRef = pNode->mpNodeParent;
370 if(pNode == pNodeRightmostRef)
374 if(pNode->mpNodeLeft)
375 pNodeRightmostRef = RBTreeGetMaxChild(pNodeChild);
377 pNodeRightmostRef = pNode->mpNodeParent;
384 pNode->mpNodeLeft->mpNodeParent = pNodeSuccessor;
385 pNodeSuccessor->mpNodeLeft = pNode->mpNodeLeft;
387 if(pNodeSuccessor == pNode->mpNodeRight)
388 pNodeChildParent = pNodeSuccessor;
391 pNodeChildParent = pNodeSuccessor->mpNodeParent;
394 pNodeChild->mpNodeParent = pNodeChildParent;
396 pNodeChildParent->mpNodeLeft = pNodeChild;
398 pNodeSuccessor->mpNodeRight = pNode->mpNodeRight;
399 pNode->mpNodeRight->mpNodeParent = pNodeSuccessor;
402 if(pNode == pNodeRootRef)
403 pNodeRootRef = pNodeSuccessor;
404 else if(pNode == pNode->mpNodeParent->mpNodeLeft)
405 pNode->mpNodeParent->mpNodeLeft = pNodeSuccessor;
407 pNode->mpNodeParent->mpNodeRight = pNodeSuccessor;
411 pNodeSuccessor->mpNodeParent = pNode->mpNodeParent;
412 eastl::swap(pNodeSuccessor->mColor, pNode->mColor);
416 if(pNode->mColor == kRBTreeColorBlack)
418 while((pNodeChild != pNodeRootRef) && ((pNodeChild == NULL) || (pNodeChild->mColor == kRBTreeColorBlack)))
420 if(pNodeChild == pNodeChildParent->mpNodeLeft)
424 if(pNodeTemp->mColor == kRBTreeColorRed)
426 pNodeTemp->mColor = kRBTreeColorBlack;
427 pNodeChildParent->mColor = kRBTreeColorRed;
429 pNodeTemp = pNodeChildParent->mpNodeRight;
432 if(((pNodeTemp->mpNodeLeft == NULL) || (pNodeTemp->mpNodeLeft->mColor == kRBTreeColorBlack)) &&
433 ((pNodeTemp->mpNodeRight == NULL) || (pNodeTemp->mpNodeRight->mColor == kRBTreeColorBlack)))
435 pNodeTemp->mColor = kRBTreeColorRed;
436 pNodeChild = pNodeChildParent;
437 pNodeChildParent = pNodeChildParent->mpNodeParent;
441 if((pNodeTemp->mpNodeRight == NULL) || (pNodeTemp->mpNodeRight->mColor == kRBTreeColorBlack))
443 pNodeTemp->mpNodeLeft->mColor = kRBTreeColorBlack;
444 pNodeTemp->mColor = kRBTreeColorRed;
446 pNodeTemp = pNodeChildParent->mpNodeRight;
449 pNodeTemp->mColor = pNodeChildParent->mColor;
450 pNodeChildParent->mColor = kRBTreeColorBlack;
452 if(pNodeTemp->mpNodeRight)
453 pNodeTemp->mpNodeRight->mColor = kRBTreeColorBlack;
464 if(pNodeTemp->mColor == kRBTreeColorRed)
466 pNodeTemp->mColor = kRBTreeColorBlack;
467 pNodeChildParent->mColor = kRBTreeColorRed;
470 pNodeTemp = pNodeChildParent->mpNodeLeft;
473 if(((pNodeTemp->mpNodeRight == NULL) || (pNodeTemp->mpNodeRight->mColor == kRBTreeColorBlack)) &&
474 ((pNodeTemp->mpNodeLeft == NULL) || (pNodeTemp->mpNodeLeft->mColor == kRBTreeColorBlack)))
476 pNodeTemp->mColor = kRBTreeColorRed;
477 pNodeChild = pNodeChildParent;
478 pNodeChildParent = pNodeChildParent->mpNodeParent;
482 if((pNodeTemp->mpNodeLeft == NULL) || (pNodeTemp->mpNodeLeft->mColor == kRBTreeColorBlack))
484 pNodeTemp->mpNodeRight->mColor = kRBTreeColorBlack;
485 pNodeTemp->mColor = kRBTreeColorRed;
488 pNodeTemp = pNodeChildParent->mpNodeLeft;
491 pNodeTemp->mColor = pNodeChildParent->mColor;
492 pNodeChildParent->mColor = kRBTreeColorBlack;
494 if(pNodeTemp->mpNodeLeft)
495 pNodeTemp->mpNodeLeft->mColor = kRBTreeColorBlack;
504 pNodeChild->mColor = kRBTreeColorBlack;
EASTL_API void RBTreeErase(rbtree_node_base *pNode, rbtree_node_base *pNodeAnchor)
rbtree_node_base * RBTreeRotateLeft(rbtree_node_base *pNode, rbtree_node_base *pNodeRoot)
EASTL_API size_t RBTreeGetBlackCount(const rbtree_node_base *pNodeTop, const rbtree_node_base *pNodeBottom)
EASTL_API rbtree_node_base * RBTreeIncrement(const rbtree_node_base *pNode)
rbtree_node_base * RBTreeRotateRight(rbtree_node_base *pNode, rbtree_node_base *pNodeRoot)
EASTL_API void RBTreeInsert(rbtree_node_base *pNode, rbtree_node_base *pNodeParent, rbtree_node_base *pNodeAnchor, RBTreeSide insertionSide)
EASTL_API rbtree_node_base * RBTreeDecrement(const rbtree_node_base *pNode)
EA Standard Template Library.