新增AI编程课程，引领技术教育新趋势
首先说一下，关于红黑树有一篇很棒的论文《A dichromatic framework for balanced trees》，作者之一的Robert Sedgewick，想必大家不会陌生。如果有兴趣可以仔细研读一下，里面讲了更多细节的分析，而本文也借鉴了其中的一些思路和配图。
回顾一下之前的结构分析，经验指出：平均而言红黑树大约和AVL树一样深，如此保证了查找效率接近最优。另外他的优点有两个，插入所需要的开销比之前更低，再有就是实践中发生的旋转相对比较少。
而红黑树的具体实现是比较复杂的，这不仅因为可能会发生大量的旋转，还因为一些子树可能是空的（比如10这个节点的右子树），以及处理根的特殊情况（因为没有父节点）。因此我们要用两个标记节点：一个是根；一个是NullNode，类似在伸展树里指示NULL的指针。根标记用来储存
#ifndef RB_Tree_h #define RB_Tree_h typedef enum{ red,black} Color; const int Infinity = 0x3f3f3f3f; const int NegINF = -Infinity -1; struct RedBlackNode; typedef RedBlackNode* RedBlackTree; typedef RedBlackNode* Position; struct RedBlackNode { int value,Height; RedBlackTree left; RedBlackTree right; Color col; }; Position NullNode=NULL; //needs initializationint max(int a,int b){ return a>b?a:b;} RedBlackTree Insert(int Item,RedBlackTree T); RedBlackTree Delete(int Item,RedBlackTree T); #endif /* RB_Tree_h *///下面这些看着一大堆，其实都是之前学过的那些基本操作，都是纸老虎233static int Height( Position P ) { return P==NULL?-1:P->Height; } static Position SingleRotateWithLeft( Position p ) //左-左的情况{ Position temp; temp = p->left; p->left = temp->right; temp->right = p; p->Height = max( Height( p->left ), Height( p->right ) ) + 1; temp->Height = max( Height( temp->left ), p->Height ) + 1; return temp; /* New root */ } static Position SingleRotateWithRight( Position g ) //右-右的情况{ Position temp; temp = g->right; g->right = temp->left; temp->left = g; g->Height = max( Height( g->left ), Height( g->right ) ) + 1; temp->Height = max( Height( temp->right ), g->Height ) + 1; return temp; /* New root */ }
NullNode标记含义有所变化，为此调整一下打印函数，用一个隐藏的递归过程，这样就很巧妙了，因为不会强迫用户传入T-> right，这留给机器去做。
0532-85025005
