红黑树的插入

#include "stdafx.h"
#include <iostream>
#include <Windows.h>
using namespace std;

typedef struct _Node
{
    int data;
    struct _Node *left;
    struct _Node *right;
    bool isRed;          //红黑树
    _Node()
    {
        data = 0;
        left = NULL;
        right = NULL;
        isRed = true;
    }
}Node, *_PNode;

//BST节点的查找
bool BSTSearch(_PNode pRoot, int key)
{
    while (NULL != pRoot)
    {
        if (pRoot->data == key)
        {
            return true;
        }
        else if (pRoot->data > key)
        {
            pRoot = pRoot->left;
        }
        else
        {
            pRoot = pRoot->right;
        }
    }
    return false;
}

//******************************************RBTree***********************************************begin
//参考 维基百科     : http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91
//                 http://www.cnblogs.com/abatei/archive/2008/12/17/1356565.html

//左旋
_PNode RBTreeRRTree(_PNode pNode)
{
    _PNode pNewNode = pNode->right;
    pNode->right = pNewNode->left;
    pNewNode->left = pNode;
    return pNewNode;
}

//右旋
_PNode RBTreeLLTree(_PNode pNode)
{
    _PNode pNewNode = pNode->left;
    pNode->left = pNewNode->right;
    pNewNode->right = pNode;
    return pNewNode;
}

//先右旋再左旋
_PNode RBTreeLRTree(_PNode pNode)
{
    _PNode pLeft = pNode->left;
    _PNode pNewNode = pLeft->right;
    pLeft->right = pNewNode->left;
    pNode->left = pNewNode->right;
    pNewNode->left = pLeft;
    pNewNode->right = pNode;
    return pNewNode;
}

//先左旋再右旋
_PNode RBTreeRLTree(_PNode pNode)
{
    _PNode pRight = pNode->right;
    _PNode pNewNode = pRight->left;
    pRight->left = pNewNode->right;
    pNode->right = pNewNode->left;
    pNewNode->left = pNode;
    pNewNode->right = pRight;
    return pNewNode;
}
_PNode pRBTreeRoot = NULL;    //红黑树的根节点
_PNode path[20];
//插入节点
void RBTreeInsertNode(int key)
{
    if (BSTSearch(pRBTreeRoot, key))  //找到，不能插入直接返回
    {
        return;
    }
    _PNode pNode = new Node;
    pNode->data = key;
    if (NULL == pRBTreeRoot)
    {
        pRBTreeRoot = pNode;
        pRBTreeRoot->isRed = false;
        return;
    }
    int top = 0;
    _PNode p = pRBTreeRoot;
    while (NULL != p)
    {
        path[top++] = p;
        if (key < p->data)
        {
            p = p->left;
        }
        else if (key > p->data)
        {
            p = p->right;
        }
    }
    _PNode father = path[top - 1];
    if (key < father->data)
    {
        father->left = pNode;
    }
    else if (key > father->data)
    {
        father->right = pNode;
    }
    if (!father->isRed)    //父节点是黑色，直接返回
    {
        return;
    }
    path[top] = pNode;
    while ((top -= 2) >= 0)
    {
        _PNode grandfather = path[top];
        father = path[top + 1];
        _PNode current = path[top + 2];
        _PNode uncle;
        
        if (!father->isRed)    //父节点是黑色，直接返回
        {
            break;
        }
        if (grandfather->left == father)
        {
            uncle = grandfather->right;
        }
        else
        {
            uncle = grandfather->left;
        }
        if (NULL != uncle && uncle->isRed)  //父节点是红色，叔父节点不空，而且为红色
        {
            father->isRed = false;
            uncle->isRed = false;
            if (top > 0)
            {
                grandfather->isRed = true;
            }
        }
        else         //父节点是红色，叔父节点为黑色或者为空的情况
        {
            _PNode pNewNode;
            if (grandfather->left == father)
            {
                if (father->left == current)
                {
                    pNewNode = RBTreeLLTree(grandfather);
                }
                else
                {
                    pNewNode = RBTreeLRTree(grandfather);
                }
            }
            else
            {
                if (father->left == current)
                {
                    pNewNode = RBTreeRLTree(grandfather);
                }
                else
                {
                    pNewNode = RBTreeRRTree(grandfather);
                }
            }
            grandfather->isRed = true;  //祖父节点变为红色
            pNewNode->isRed = false;    //新节点变为黑色
            if (top > 0)
            {
                if (path[top - 1]->left == grandfather)
                {
                    path[top - 1]->left = pNewNode;
                }
                else
                {
                    path[top - 1]->right = pNewNode;
                }
            }
            else
            {
                pRBTreeRoot = pNewNode;
            }
            return;
        }
    }
}
//******************************************RBTree***********************************************end

//辅助函数，设置控制台的颜色
void SetConsoleTextColor(WORD dwColor)
{
    HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);
    if (INVALID_HANDLE_VALUE == handle)
    {
        return;
    }
    SetConsoleTextAttribute(handle, dwColor);
}


//前序递归遍历
void PreRecurTraversal(_PNode pRoot)
{
    if (NULL != pRoot)
    {
        if (pRoot->isRed)
        {
            SetConsoleTextColor(FOREGROUND_RED | FOREGROUND_INTENSITY);
            cout<<pRoot->data<<"  ";
        }
        else
        {
            SetConsoleTextColor(FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY);
            cout<<pRoot->data<<"  ";
        }
        PreRecurTraversal(pRoot->left);
        PreRecurTraversal(pRoot->right);
    }
}

//中序递归遍历
void MidRecurTraversal(_PNode pRoot)
{
    if (NULL != pRoot)
    {
        MidRecurTraversal(pRoot->left);
        if (pRoot->isRed)
        {
            SetConsoleTextColor(FOREGROUND_RED | FOREGROUND_INTENSITY);
            cout<<pRoot->data<<"  ";
        }
        else
        {
            SetConsoleTextColor(FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE | FOREGROUND_INTENSITY);
            cout<<pRoot->data<<"  ";
        }
        MidRecurTraversal(pRoot->right);
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    cout<<"******************建立RBTree二叉树********************"<<endl;
    int a[10] = {6, 7, 2, 1, 9, 5, 3, 10, 8, 4};
    for (int i = 0; i < 10; i++)
    {
        RBTreeInsertNode(a[i]);
    }
    SetConsoleTextColor(FOREGROUND_GREEN | FOREGROUND_INTENSITY);
    cout<<"前序输出： ";
    PreRecurTraversal(pRBTreeRoot);
    SetConsoleTextColor(FOREGROUND_GREEN | FOREGROUND_INTENSITY);
    cout<<endl<<"中序输出： ";
    MidRecurTraversal(pRBTreeRoot);
    cout<<endl;
    return 0;
}

界面运行如下，红色为红节点，白色为黑节点

构造的红黑树如下：