免费网络营销课程_深圳卓越城蔚蓝铂樾府_网站打开速度优化_seo哪里有培训

目录

一、什么是红黑树

1.1 红黑树的规则

1.2 红黑树的特性

二、红黑树的插入

2.0 插入思路

2.1 情况一

2.2 情况二

2.3 情况三

2.2 插入代码

---

一、什么是红黑树

红黑树是一种特殊的二叉搜索树，它在每个节点上增加了一个颜色属性，可以是红色或黑色。

1.1 红黑树的规则

• 每个节点要么是黑色要么是红色。
• 根节点是黑色。
• 每个叶子节点（NIL节点，空节点）是黑色。
• 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
• 如果⼀个结点是红⾊的，则它的两个孩⼦结点必须是黑色的，也就是说任意⼀条路径不会有连续的红⾊结点。

enum colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;colour _col;//三叉链RBTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}
};

1.2 红黑树的特性

假设从根节点开始到NULL节点最短的路径高度为bh，则红黑树的总高度h满足：bh <= h <= 2*bh。

二、红黑树的插入

2.0 插入思路

总体思路：

• 先按照搜索二叉树的规则进行插入，然后通过一系列操作使之满足红黑树的规则。
• 如果是空树插入，新增结点是黑色结点。如果是非空树插⼊，新增结点必须红色结点。

  if (_root == nullptr)
  {_root = new Node(kv);_root->_col = BLACK;return true;
  }
  Node* parent = nullptr;
  Node* cur = _root;
  while (cur)
  {if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}
  }cur = new Node(kv);
  cur->_col = RED;
  if (parent->_kv.first < kv.first)
  {parent->_right = cur;
  }
  else
  {parent->_left = cur;
  }
  //链接父亲
  cur->_parent = parent;

• 插入后，如果其父亲节点是黑色的，则满足红黑树的规则。如果父亲节点是红色的，则不满足（红色节点的子节点都为黑色）的规则，需要调整。

2.1 情况一

叔叔节点存在且为红色

• 考虑一般情况：
  让“叔叔”节点变为黑色，“爷爷”节点变为红色 ，“父亲”节点变为黑色
• 考虑特殊情况：
  插入的树可能只是其中的一颗子树，爷爷节点的颜色变化可能会违反规则
  所以，将cur指向爷爷节点，继续进行处理

Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;
}

2.2 情况二

• 叔叔节点不存在
  cur指向的一定是新增的节点
  
• 叔叔节点存在但是为黑色
  cur指向的一定不是新增的节点，而是某个子树新增了节点导致其爷爷节点变成了红色
  

如果父亲在爷爷的左边：则右旋

如果父亲在爷爷的右边：则左旋

最后：父亲节点变黑，爷爷节点变红

//父亲在爷爷的左树
if (cur == parent->_left)
{RotateR(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;
}
//父亲在爷爷的右树
if (cur == parent->_right)
{RotateL(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;
}

2.3 情况三

• 叔叔节点不存在
  cur指向的一定是新插入的节点
  
• 叔叔节点存在但是为黑色
  cur指向的一定不是新增的节点，而是某个子树新增了节点导致其爷爷节点变成了红色
  

//父亲节点在爷爷节点的左边
RotateL(parent);
RotateR(grandfather);
//变色
cur->_col = BLACK;
grandfather->_col = RED;//父亲节点在爷爷节点的右边
RotateR(parent);
RotateL(grandfather);
//变色
cur->_col = BLACK;
grandfather->_col = RED;

2.2 插入代码

旋转部分代码详见：数据结构之AVL树（万字详解）_avl树 详解-CSDN博客

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}//链接父亲cur->_parent = parent;//父亲是红色、处理while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (grandfather->_left==parent){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_left){RotateR(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);//变色cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){RotateL(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);//变色cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;
}