红黑树Red Black Tree

红黑树的详细描述，从数据结构到创建，最小值，最大值，后继，遍历，插入以及删除。 该代码是clion IDE中实现的，代码全部在main.c中。

#include 
#include 


typedef int ElemType;
typedef enum {RED BLACK} Color;
//structure
// node of the tree
typedef struct Node{
    Color color;
    struct Node *left;
    struct Node *right;
    struct Node *p;
    ElemType key;
}Node;


// red black tree
typedef struct Tree{
    Node *nillNode;
    Node * root;
}*RedBlackTree;

// find the min key with x as the root
Node * min（RedBlackTree t Node * x） {
    if （x != t->nillNode） {
        Node *y = x->left;
        while （y != t->nillNode） {
            x = y;
            y = x->left;
        }
    }
    return x;
}
// find the max key with x as the root
Node * max（RedBlackTree t Node *x） {
    if （x != t->nillNode） {
        Node *y = x->right;
        while （y != t->nillNode） {
            x = y;
            y = x->right;
        }
    }
    return x;
}

Node *successor（RedBlackTree t Node * x） {
    if（x->right != t->nillNode） {
        return min（t x->right）;
    }
    Node * y = x->p;
    while （y != t->nillNode && x == y->left） {
        x = y;
        y = y->p;
    }
    return y;
}
// create red black tree and initial
void createTree（RedBlackTree *t） {
    // global nil node
    Node * nillNode = NULL;
    // create nillNode and initial
    nillNode = （Node *）malloc（sizeof（Node））;
    if（nillNode == NULL） {
        printf（“nilNode allocation failed!\n“）;
        exit（1）;
    }
    nillNode->color = BLACK;
    nillNode->left = NULL;
    nillNode->right = NULL;
    nillNode->p = NULL;

    //create Red Black Tree and initial
    （*t） = （RedBlackTree） malloc（sizeof（struct Tree））;
    if（*t == NULL） {
        printf（“red black allocation failed!\n“）;
        exit（-1）;
    }
    （*t）->root = nillNode;
    （*t）->nillNode = nillNode;
}

void leftRotate（RedBlackTree t Node *x） {
    // Suppose the right node exists（right node not null）
    Node * y = x->right;
    //turn y‘s left subtree into x‘s right subtree
    x->right = y->left;
    if（y->left != t->nillNode） {
        y->left->p = x;
    }
    y->p = x->p;
    if（x->p == t->nillNode） {      // x is the root of the tree
        t->root = y;
    } else if （x == x->p->left） {
        x->p->left = y;
    } else {
        x->p->right = y;
    }

    // put x on y‘s leftg
    y->left = x;
    // link x->p to y
    x->p = y;
}

void rightRotate（RedBlackTree t Node *x） {
    Node *y = x->left;
    x->left = y->right;
    if（y->left != t->nillNode） {
        y->right->p = x;
    }
    y->p = x->p;
    if（x->p == t->nillNode） {
        t->root = y;
    } else if （x == x->p->left） {
        x->p->left = y;
    } else {
        x->p->right = y;
    }
    y->right = x;
    x->p = y;
}

// used for fix up when insert
void insertFixUp（RedBlackTree t Node *z） {
    Node * y = t->nillNode;
    while （z->p->color == RED） {
        if（z->p == z->p->p->left） {
            // find z‘s uncle node
            y = z->p->p->right;
            // case 1
            if （y->color == RED） {
                z->p->color = BLACK;
            

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        137  2017-01-18 20:46  RedBlackTree\.idea\misc.xml

     文件        276  2017-01-18 20:45  RedBlackTree\.idea\modules.xml

     文件         97  2017-01-18 20:46  RedBlackTree\.idea\RedBlackTree.iml

     文件      27200  2017-01-27 17:20  RedBlackTree\.idea\workspace.xml

     文件      34567  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeCache.txt

     文件       2151  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\3.6.3\CMakeCCompiler.cmake

     文件       4703  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\3.6.3\CMakeCXXCompiler.cmake

     文件      60657  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\3.6.3\CMakeDetermineCompilerABI_C.bin

     文件      60552  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\3.6.3\CMakeDetermineCompilerABI_CXX.bin

     文件        234  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\3.6.3\CMakeRCCompiler.cmake

     文件        395  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\3.6.3\CMakeSystem.cmake

     文件      60777  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\3.6.3\CompilerIdC\a.exe

     文件      17387  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\3.6.3\CompilerIdC\CMakeCCompilerId.c

     文件      60691  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\3.6.3\CompilerIdCXX\a.exe

     文件      16930  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\3.6.3\CompilerIdCXX\CMakeCXXCompilerId.cpp

     文件        108  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\clion-environment.txt

     文件        917  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\clion-log.txt

     文件         86  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\cmake.check_cache

     文件        670  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\CMakeDirectoryInformation.cmake

     文件      49455  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\CMakeOutput.log

     文件      62055  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\feature_tests.bin

     文件        722  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\feature_tests.c

     文件      10416  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\feature_tests.cxx

     文件      11857  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\Makefile.cmake

     文件       3479  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\Makefile2

     文件          3  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\progress.marks

     文件       4934  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\RedBlackTree.dir\build.make

     文件        224  2017-01-27 17:20  RedBlackTree\cmake-build-debug\CMakeFiles\RedBlackTree.dir\C.includecache

     文件        332  2017-01-18 20:45  RedBlackTree\cmake-build-debug\CMakeFiles\RedBlackTree.dir\cmake_clean.cmake

     文件        183  2017-01-27 17:20  RedBlackTree\cmake-build-debug\CMakeFiles\RedBlackTree.dir\depend.internal

............此处省略28个文件信息