2015.7.5 计划开启，每日更新进度，以此鞭策自己
书单
算法导论
Javascript高级程序设计
进度
算法导论
红黑树
旋转的本质：中序遍历键值顺序一致
左旋：即以x的右子为父节点，x的新右子为原右子的左节点，最后令新父节点的左节点为x
右旋：即以x的左子为父节点，x的新左子为原左子的右节点，最后令新父节点的右节点为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
红黑树插入结点
新插入结点置为红结点，有且仅有两种违反红黑树性质的情况
- 根结点为红色（即新插入结点为根节点）
- 新插入结点的父节点为红色
因此分三种情况调整
- z结点的叔父结点为红结点
可将z的父结点及叔父结点变为黑色，将z的祖父结点变为红色，最后将z上移至祖父结点；下一次调整
- z结点为右子，且叔父结点为黑色
将z上移至父结点，以z（原z的父节点）为轴，左旋；变为情况3
- z结点为左子，且叔父结点为黑色
将z的父结点变为黑色，祖父结点变为红色，将z上移至祖父结点，并以z为轴右旋；下一次调整
实现
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;
}