#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個文件信息