2015.7.5 計(jì)劃開啟吹艇，每日更新進(jìn)度，以此鞭策自己

書單

1. 算法導(dǎo)論

2. Javascript高級(jí)程序設(shè)計(jì)

進(jìn)度

算法導(dǎo)論

紅黑樹

旋轉(zhuǎn)的本質(zhì)：中序遍歷鍵值順序一致

左旋：即以x的右子為父節(jié)點(diǎn)，x的新右子為原右子的左節(jié)點(diǎn)，最后令新父節(jié)點(diǎn)的左節(jié)點(diǎn)為x

右旋：即以x的左子為父節(jié)點(diǎn)，x的新左子為原左子的右節(jié)點(diǎn)辫红，最后令新父節(jié)點(diǎn)的右節(jié)點(diǎn)為x

rightRotate pseudocode

RightFloat(T, x)
    y = left[x]
    left[x] = right[y]
    
    if right[y] != NULL
        p[right[y]] = x
    
    p[y] = p[x]
    
    if p[x] == NULL
        root[T] = y
    else
        if x == left[p[x]]
            left[p[x]] = y
        else
            right[p[x]] = y
    
    right[y] = x
    p[x] = y

紅黑樹插入結(jié)點(diǎn)

新插入結(jié)點(diǎn)置為紅結(jié)點(diǎn)，有且僅有兩種違反紅黑樹性質(zhì)的情況

1. 根結(jié)點(diǎn)為紅色（即新插入結(jié)點(diǎn)為根節(jié)點(diǎn)）
2. 新插入結(jié)點(diǎn)的父節(jié)點(diǎn)為紅色

因此分三種情況調(diào)整

1. z結(jié)點(diǎn)的叔父結(jié)點(diǎn)為紅結(jié)點(diǎn)

可將z的父結(jié)點(diǎn)及叔父結(jié)點(diǎn)變?yōu)楹谏＠保瑢的祖父結(jié)點(diǎn)變?yōu)榧t色贴妻，最后將z上移至祖父結(jié)點(diǎn)；下一次調(diào)整

2. z結(jié)點(diǎn)為右子蝙斜，且叔父結(jié)點(diǎn)為黑色

將z上移至父結(jié)點(diǎn)名惩，以z（原z的父節(jié)點(diǎn)）為軸，左旋孕荠；變?yōu)榍闆r3

3. z結(jié)點(diǎn)為左子娩鹉，且叔父結(jié)點(diǎn)為黑色

將z的父結(jié)點(diǎn)變?yōu)楹谏娓附Y(jié)點(diǎn)變?yōu)榧t色稚伍，將z上移至祖父結(jié)點(diǎn)弯予，并以z為軸右旋；下一次調(diào)整

實(shí)現(xiàn)

TreeNode Definition

struct TreeNode {
    TreeNode():color(true),left(NULL),right(NULL),p(NULL) {}
    TreeNode(int key):key(key),color(true),left(NULL),right(NULL),p(NULL) {}

    bool color; // true: red | false: black
    int key;
    TreeNode* left;
    TreeNode* right;
    TreeNode* p;
};

LeftRotate Implementation

/**
 * assert root->p == NULL && x->right != NULL
 * 
 * @param Tree root node
 * @param Left Rotate node
 */
void leftRotate(TreeNode** root, TreeNode* x) {
    TreeNode* y = x->right;

    // adjust x's right child, i.e. y's left child
    x->right = y->left;
    if (y->left != NULL)
        y->left->p = x;

    // adjust parent child
    y->p = x->p;
    if (x->p == NULL)
        *root = y;
    else
        if (x->p->left == x)
            x->p->left = y;
        else
            x->p->right = y;

    // adjust y's left child, i.e. x
    y->left = x;
    x->p = y;
}

RightRotate Implementation

/**
 * assert root->p == NULL && x->left != NULL
 * 
 * @param Tree root node
 * @param Right Rotate node
 */
void rightRotate(TreeNode** root, TreeNode* x) {
    TreeNode* y = x->left;

    // adjust y right subtree to x left
    x->left = y->right;
    if (y->right != NULL)
        y->right->p = x;

    // adjust parent
    y->p = x->p;
    if (x->p == NULL)
        *root = y;
    else
        if (x->p->left == x)
            x->p->left = y;
        else
            x->p->right = y;

    // push x to y right child
    y->right = x;
    x->p = y;
}

RBInsert Implementation

/**
 * @param
 */
void rBInsert(TreeNode** root, TreeNode* z) {
    TreeNode* y = NULL;
    TreeNode* x = *root;

    while (x != NULL) {
        y = x;
        if (z->key < x->key)
            x = x->left;
        else
            x = x->right;
    }

    z->p = y;

    if (y == NULL)
        *root = z;
    else
        if (z->key < y->key)
            y->left = z;
        else
            y->right = z;

    rbInsertFixUp(root, z);
}

RB-Insert-FIXUP Implementation

/**
 * @param root [description]
 * @param z    [description]
 */
void rbInsertFixUp(TreeNode** root, TreeNode* z) {
    while (z->p != NULL && z->p->color) { // p[z] = red
        TreeNode* y = z->p->p;
        if (y->left == z->p) {
            if (y->right != NULL && y->right->color) { // p[p[z]].right = red
                z->p->color = false;
                y->right->color = false;
                y->color = true;
                z = y;
            } else {
                if (z->p->right == z) {
                    z = z->p;
                    leftRotate(root, z);
                }
                z->p->color = false;
                y->color = true;
                z = y;
                rightRotate(root, z);
            }
        }
        else { // symmetry
            if (y->left != NULL && y->left->color) { // p[p[z]].left = red
                z->p->color = false;
                y->left->color = false;
                y->color = true;
                z = y;
            } else {
                if (z->p->left == z) {
                    z = z->p;
                    rightRotate(root, z);
                }
                z->p->color = false;
                y->color = true;
                z = y;
                leftRotate(root, z);
            }
        }
    }
    (*root)->color = false;
}

BFS for test Implementation

/**
 * @param Tree root node
 */
void BFS(TreeNode* root) {
    if (root == NULL)
        return;

    std::queue<TreeNode*> queue;
    queue.push(root);

    while (!queue.empty()) {
        TreeNode* cur = queue.front();
        queue.pop();

        printf("%d ", cur->key);

        if (cur->left != NULL)
            queue.push(cur->left);

        if (cur->right != NULL)
            queue.push(cur->right);
    }
}

Exercise 13.3.2

/**
 * Exercise 13.3.2
 */
int main(int argc, char const *argv[]) {
    TreeNode* root = NULL;
    TreeNode node1(41);
    TreeNode node2(38);
    TreeNode node3(31);
    TreeNode node4(12);
    TreeNode node5(19);
    TreeNode node6(8);

    rBInsert(&root, &node1);
    rBInsert(&root, &node2);
    rBInsert(&root, &node3);
    rBInsert(&root, &node4);
    rBInsert(&root, &node5);
    rBInsert(&root, &node6);

    BFS(root);

    return 0;
}