#include"RBtree.h"

RBtree::treenode* RBtree::find(int val)

{

if (nodecount == 0) return nullptr;

treenode* temp = head->parent;

while (temp->value != val)

{

while (temp != nullptr && temp->value > val) temp = temp->left;

while (temp != nullptr && temp->value < val) temp = temp->right;

if (temp == nullptr) return nullptr;

}

return temp;

}

void RBtree::clearall(treenode* root)

{

if (root == nullptr) return;

clearall(root->left);

clearall(root->right);

delete root;

}

void RBtree::print(treenode* node)

{

if (node == nullptr) return;

print(node->left);

std::cout << node->value << " ";

print(node->right);

}

RBtree::treenode* RBtree::find_larger(treenode* node)

{

if (node == head->right) return nullptr;//已是最大节点

if (node->right != nullptr)

{

node = node->right;

while (node->left != nullptr)

node = node->left;

return node;

}

else

{

treenode* p = node->parent;

while (p->right == node)

{

node = p;

p = p->parent;

}

if (node->right != p)

node = p;

return node;

}

}

RBtree::treenode* RBtree::find_smaller(treenode* node)

{

if (node == head->left) return nullptr; //已是最小节点

if (node->left != nullptr)

{

node = node->left;

while (node->right != nullptr)

node = node->right;

return node;

}

else

{

treenode* p = node->parent;

while (p->left == node)

{

node = p;

p = p->parent;

}

return p;

}

}

/*

r2插入在r1左子节点违反规则,对b右旋转

改变r1和b的颜色(在之后的rebalance调整里进行，rotate函数只进行旋转.)

假设A,B为nullptr

b r1 b(r1)

/ \ / \ / \

r1 A ==> r2 b ==> r2 r3(b)

/ \ / \ / \

r2 B B A B A

*/

void RBtree::right_rotate(treenode* node)

{

treenode*& root = head->parent;

treenode* r1 = node->left;

node->left = r1->right;

if (r1->right != nullptr) //set parent

r1->right->parent = node;

r1->parent = node->parent;

if (node == root) //set root

root = r1;

else if (node == node->parent->right)

node->parent->right = r1;

else

node->parent->left = r1;

r1->right = node;

node->parent = r1;

}

void RBtree::left_rotate(treenode* node)

{

treenode*& root = head->parent;

treenode* r1 = node->right;

node->right = r1->left;

if (r1->left != nullptr)

r1->left->parent = node;

r1->parent = node->parent;

if (node == root)

root = r1;

else if (node == node->parent->left)

node->parent->left = r1;

else

node->parent->right = r1;

r1->left = node;

node->parent = r1;

}

RBtree::treenode* RBtree::insert(const int val)

{

if (nodecount == 0)

{

nodecount++;

head->parent = new treenode(head, val, 'b');

head->left = head->parent;

head->right = head->parent;

return head->parent;

}

treenode* y = head;

treenode* x = head->parent;

while (x != nullptr)

{

y = x;

x = val < x->value ? x->left : x->right;

}

treenode* p = y;

if (val < y->value)

{

if (p == head->left)

return insert_unique(x, y, val);

else

p = find_smaller(p);

}

if (val > p->value)

return insert_unique(x, y, val);

//值重复,不插入,返回空指针

return nullptr;

}

RBtree::treenode* RBtree::insert_unique(treenode* x, treenode* y, const int val)

{

treenode* newnode = new treenode(y, val, 'r');

if (y == head || x != 0 || val < y->value)

{

y->left = newnode;

if (y == head)

{

head->parent = head->right;

head->right = newnode;

}

else if (y == head->left)

head->left = y->left;

}

else

{

y->right = newnode;

if (y == head->right)

head->right = newnode;

}

nodecount++;

rebanlance(newnode);//调整新插入的节点

return newnode;

}

void RBtree::rebanlance(treenode* node)

{

treenode*& root = head->parent;

while (node != root && node->parent->color == 'r')

{

if (node->parent == node->parent->parent->left)

{

treenode* temp = node->parent->parent->right;

if (temp && temp->color == 'r')

{

node->parent->color = 'b';

temp->color = 'b';

node->parent->parent->color = 'r';

node = node->parent->parent;

}

else

{

if (node == node->parent->right)

{

node = node->parent;

left_rotate(node);

}

node->parent->color = 'b';

node->parent->parent->color = 'r';

right_rotate(node->parent->parent);

}

}

else

{

treenode* temp = node->parent->parent->left;

if (temp && temp->color == 'r')

{

node->parent->color = 'b';

temp->color = 'b';

node->parent->parent->color = 'r';

node = node->parent->parent;

}

else

{

if (node == node->parent->left)

{

node = node->parent;

right_rotate(node);

}

node->parent->color = 'b';

node->parent->parent->color = 'r';

left_rotate(node->parent->parent);

}

}

}

root->color = 'b';

}

int main(int argc, char const *argv[])

{

RBtree rbtree;

rbtree.insert(10);

rbtree.insert(9);

rbtree.insert(10);

rbtree.insert(33);

rbtree.insert(0);

rbtree.insert(-2);

rbtree.insert(32);

//-2 0 9 10 32 33

rbtree.printbyorder();

return 0;

}