红黑树c语言实现.pdfVIP

//红黑树c语言手打版，未测试 #include stdio.h enum Color { black = 0, red = 1 }; typedef int RB_Tree_Data; //定义节点数据类型 typedef struct RB_Tree //定义红黑树节点类型 { Color color; RB_Tree* lChild; RB_Tree* rChild; RB_Tree_Data data; RB_Tree*parent; RB_Tree* nil; } RB_N, *RB_P; /*定义NIL公用叶节点*/ const RB_N NIL = { black, NULL, NULL, 0, NULL}; //返回最小节点 RB_P RB_MIN(RB_P p) { RB_P q = p; if ((RB_P)NIL != q-lChild) { q = q-lChild; } return q; } /* 向右旋转*/ void Right_Rotate(RB_P* head ,RB_P h, RB_P*p) { RB_P h1 = *head; RB_P q = (*p)-lChild; (*p)-lChild = q-rChild; if (q-rChild != h-nil) q-rChild-parent = (*p); q-parent = (*p)-parent; if ((*p)-parent == h-parent) //判断是否为根节点 h1 = q; else if ((*p) == (*p)-parent-lChild) //判断是否是左枝 (*p)-parent-lChild = q; else (*p)-parent-rChild = q; q-rChild = (*p); (*p)-parent = q; } /* 向左旋转*/ void Letf_Rotate(RB_P *head, RB_P h, RB_P*p) { RB_P h1 = *head; RB_P q = (*p)-rChild; (*p)-rChild = q-lChild; if (q-lChild != h-nil) q-lChild-parent = (*p); q-parent = (*p)-parent; if ((*p)-parent == h-parent) //判断是否为根节点 h1 = q; else if ((*p) == (*p)-parent-lChild) // 判断是否是左枝 (*p)-parent-lChild = q; else (*p)-parent-rChild = q; q-lChild = (*p); (*p)-parent = q; } /*插入维护*/ void RB_Insert_FIXUP(RB_P*head, RB_P location, RB_P z) { RB_P h = *head; while (red == z-parent-color) { if (z-parent == z-parent-parent-lChild) { RB_P y = z-parent-parent-rChild; if (red == y-color) { z-parent-color = black; y-color = black; z-parent-parent-color = red; z = z-parent-parent; } else if (z =