红黑树|定义、左旋函数、右旋函数和对插入结点的修复

1.红黑树类的定义

enum class Color
{
RED,
BLACK
};

template<typename Key ,typename Value>
class RedBlackTree
{
class Node 
{
public:
Key key;
Value value;
Color color;
Node* left;
Node* right;
Node* parent;

Node()
:color(Color::BLACK),left(NULL),right(NULL),parent(NULL)
{}
Node(const Key&key,const Value&value,Color color,Node*p=NULL)
:key(key),value(value),color(color),left(NULL),right(NULL),parent(p)
{}
};

private:
Node* root;
size_t size;
Node* Nil;
};

2.左旋函数和右旋函数

//右旋函数
void rightRotate(Node* node)
{
Node* p = node->left;
//处理p的右孩子
node->left = p->right;
if (p->right != NULL)
p->right->parent->node;
//把p置为老大
p->parent = node->parent;
if (node->parent == NULL)
root = p;
if (node == node->parent->left)
node->parent->left = p;
else if (node == node->parent->right)
node->parent->right = p;
//让node成为p的右孩子
p->right = node;
node->parent = p;
}

//左旋函数
void leftRotate(Node* node)
{
Node* p = node->right;
node->right = p->left;
if (p->left != NULL)
p->left->parent = node;
p->parent = node->parent;
if (node->parent == NULL)
root = p;
if (node == node->parent->left)
node->parent->left = p;
else if (node == node->parent->right)
node->parent->right = p;
p->left = node;
node->parent = p;
}

3.对插入结点的修复

void insertFixup(Node*target)
{
while (target->parent != NULL && target->parent->color == Color::RED)
{
//父为祖左节点
if (target->parent = target->parent->parent->left)
{
Node* uncle = target->parent->parent->right;
//红叔
if (uncle && uncle->color == Color::RED)
{
uncle->color == Color::BLACK;
target->parent->color == Color::BLACK;
target->parent->parent->color = Color::RED;
target = target->parent->parent;
}
//黑叔
else
{
//LR
if (target == target->parent->right)
{
leftRotate(target->parent);
rightRotate(target->parent);
target->color = Color::BLACK;
target->right->color = Color::RED;
}
//LL
else if (target == target->parent->left)
{
rightRotate(target->parent->parent);
target->parent->color = Color::BLACK;
target->parent->right->color = Color::RED;
}
}
}
//父为祖的右节点
else
{
Node* uncle = target->parent->left;
//红叔
if (uncle && uncle->color == Color::RED)
{
uncle->color == Color::BLACK;
target->parent->color == Color::BLACK;
target->parent->parent->color = Color::RED;
target = target->parent->parent;
}
//黑叔
else
{
//RL
if (target == target->parent->left)
{
rightRotate(target->parent);
leftRotate(target->parent);
target->color = Color::BLACK;
target->left->color = Color::RED;
}
//RR
else if (target == target->parent->right)
{
leftRotate(target->parent->parent);
target->parent->color = Color::BLACK;
target->parent->left->color = Color::RED;
}
}
}
}
root->color = Color::BLACK;
}

原文地址：https://blog.csdn.net/2402_84438596/article/details/142568364

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！