小赵的学习笔记
0%

从AVL树到红黑树(的插入)

发表于 更新于 分类于
本文字数： 7.7k 阅读时长 ≈ 7 分钟

AVL树

  • 左右子树都是AVL树
  • 左右子树高度差的绝对值不超过1（-1/0/1）（一般：右子树高度 - 左子树高度）
  • 如果一棵二叉搜索树树高度平衡的，它就是AVL树。如果它有n个节点，其高度可保持在O(log2N)，搜索时间复杂度O(log2N)

节点结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class T>
struct AVLNode
{
	T _value;
	int _bf;//平衡因子
	AVLNode<T>* _left;
	AVLNode<T>* _right;
	AVLNode<T>* _parent;

	AVLNode(const T& val = T())
		: _value(val)
		, _bf(0)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
	{ }
}; 

插入节点后：必须要更新平衡因子

可能需要更新平衡因子的节点：

  1. 新插入节点中所有足祖先节点
  2. 如果节点的子树高度发生变化，则需要更新

插入

  1. 二叉搜索树的插入

  2. 从新插入的节点对应的父节点位置开始更新平衡因子

  3. 在第二步的过程中，平衡因子更新之后：

    1. 平衡因子：0 —-> 停止更新

    2. 平衡因子：-1/1 —-> 继续向上更新

    3. 平衡因子：-2/2 —-> 旋转

      1. 单旋：

        1. 左单旋：右边的右边高，parent->_bf == 2 && cur->_bf == 1

          修改链接：parent、subRL、subR

          ​ parent->_right : subRL、subR->left : parent

          更新平衡因子：parent、subR：0

        2. 右单旋：左边的左边高，parent->_bf == -2 && cur->_bf == -1

          修改链接：subL、subLR、parent

          ​ parent->left : subLR、subL->right : parent

          更新平衡因子：parent、subL：0

      2. 双旋：

        1. 左右双旋：左边的右边高，parent->_bf == -2 && cur->_bf == 1

          修改链接：subL、subLR、parent

          ​ 左旋：以subL为轴

          ​ 右旋：以parent为轴

          重新更新平衡因子：

          if(subLR->bf == -1)

          ​ subL->bf = 0, parent->bf = 1;

          else if(subLR->bf == 1)

          ​ subL->bf = -1, parent->bf = 0;

        2. 右左双旋右边的左边高，parent->_bf == 2 && cur->_bf == -1

          修改链接：parent、subRL、subR

          ​ 右旋：以subR为轴

          ​ 左旋：以parent为轴

          ​ 重新更新平衡因子：

          ​ if(subRL->bf == 1)

          ​ parent->bf = -1, subR->bf = 0;

          else if(subRL->bf == -1)

          ​ parent->bf = 0, subR->bf = 1;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
bool insert(const T& val)
	{
		if (_root == nullptr)
		{
			_root = new Node(val);
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			//插入
			parent = cur;
			if (cur->_value == val) {
				return false;
			}
			else if (cur->_value < val) {
				cur = cur->_right;
			}
			else {
				cur = cur->_left;
			}
		}

		cur = new Node(val);
		if (parent->_value < val) {
			parent->_right = cur;
		}else {
			parent->_left = cur;
		}

		cur->_parent = parent;

		//更新 + 调整
		while (parent)
		{
			//1.更新parent平衡因子
			if (parent->_left == cur)
				parent->_bf--;
			else
				parent->_bf++;
			//2.判断是否需要继续更新
			if (parent->_bf == 0) {//被补齐了，parent的父节点左右子树高度未发生变化
				break;
			}else if (parent->_bf == -1 || parent->_bf == 1) {
				cur = parent;
				parent = parent->_parent;
			}else if (parent->_bf == -2 || parent->_bf == 2) {
				//调整
				if (parent->_bf == -2 && cur->_bf == -1) {
					//左边的左边高，右旋
					RotateR(parent);
				} else if (parent->_bf == 2 && cur->_bf == 1) {
					//右边的右边高，左旋
					RotateL(parent);
				} else if (parent->_bf == 2 && cur->_bf == -1) {
					//右边的左边高，右左双旋
          Node* subR = parent->_right;
          Node* subRl = subR->_left;
          int bf = subRL->_bf;
          
					RotateR(cur);
					RotateL(parent);
          
          //调整平衡因子
          if(bf == 1)
          {
            //subRL右子树高
            subR->_bf = 0;
            parent->_bf = -1;
          }
          else if(bf == -1)
          {
            //subRL左子树高
            parent->_bf = 0;
            subR->_bf = 1;
          }
				} else if (parent->_bf == -2 && cur->_bf == 1) {
					//左边的右边高,左右双旋
					RotateL(cur);
					RotateR(parent);
				}

				break;
			}
		}
		return true;
	}

左旋

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		subR->_left = parent;
		parent->_right = subRL;

		if (subRL)
			subRL->_parent = parent;

		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			Node* g = parent->_parent;
			subR->_parent = g;
			if (g->_left == parent)
				g->_left = subR;
			else
				g->_right = subR;
		}

		parent->_parent = subR;
		parent->_bf = subR->_bf = 0;
	}

右旋

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		subL->_right = parent;
		parent->_left = subLR;

		if (subLR)
			subLR->_parent = parent;

		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			Node* g = parent->_parent;
			subL->_parent = g;
			if (g->_left == parent)
				g->_left = subL;
			else
				g->_right = subL;
		}
		
		parent->_parent = subL;
		parent->_bf = subL->_bf = 0;
	}

红黑树

  1. 每个节点不是红色就是黑色
  2. 根结点是黑色的
  3. 如果一个节点是红色的，则它的两个孩子节点是黑色的
  4. 对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点
  5. 每个叶子节点都是黑色的（空节点也可）

根是黑色的

红色不能连续，黑色可以连续

每条路径上，黑色节点个数相同

最长路径是最短路径的两倍（最短：全黑；最长：红黑相间）

一个红黑树的简单实现 - GitHub

节点结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
enum Color
{
	BLACK,
	RED
};

template <class K, class V>
struct RBNode
{
	pair<K, V> _value;
	Color _color;
	RBNode<K, V> _parent;
	RBNode<K, V> _left;
	RBNode<K, V> _right;

	RBNode(const pair<K, V>& value = pair<K, V>())
		: _value(value)
		, _color(RED)
		, _parent(nullptr)
		, _left(nullptr)
		, _right(nullptr)
	{ }
};

插入

不能改变当前结构中的黑色节点的个数，除了祖父节点为根节点的情况

  • g：祖父
  • p：父亲
  • u：叔叔
  • cur：插入节点
  1. 搜索树的插入
  2. 判断是否需要调整：红色连续
  • cur在p左边，叔叔存在且为红色，将p、u置为黑色，g为红色

IMG_7063

  • cur在p左边，叔叔不存在，以g为轴心进行右旋，将g变红，将p变黑

IMG_7064

  • cur在p左边叔叔为黑色，以g为轴心进行右旋，将g变红，将p变黑

IMG_7065

  • cur在p右边，先以p为轴心左旋，交换p与cur指针，按照情况三处理

IMG_7066

  • p在g右边，则操作完全相反

代码如下，其中旋转部分代码与AVL树相同：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
bool insert(const pair<K, V>& val)
 {
  if (_header->_parent == nullptr)
  {
   //空树
   Node* root = new Node(val);
   root->_color = BLACK;//根为黑色

   _header->_parent = root;
   root->_parent = _header;

   _header->_left = root;
   _header->_right = root;

   return true;
  }
  //非空树
  Node* cur = _header->_parent;
  Node* parent = nullptr;
  while (cur)
  {
   parent = cur;
   if (cur->_value.first == val.first)
    return false;
   if (cur->_value.first < val.first)
    cur = cur->_right;
   else
    cur = cur->_left;
  }

  cur = new Node(val);
  if (parent->_value.first < val.first)
   parent->_right = cur;
  else
   parent->_left = cur;

  cur->_parent = parent;

  //调整:修改颜色，旋转
  while (cur != _header->_parent && cur->_parent->_color == RED)
  {
   Node* p = cur->_parent;
   Node* g = p->_parent;
   if (g->_left == p)
   {
    Node* u = g->_right;
    if (u && u->_color == RED)
    {
     u->_color = p->_color = BLACK;
     g->_color = RED;

     cur = g;
    }
    else
    {
     //ub不存在或u存在且为黑色
     if (cur == p->_right)
     {
      RotateL(p);
      swap(cur, p);
     }

     //cur在p左边,右旋+修改颜色
     RotateR(g);
     p->_color = BLACK;
     g->_color = RED;

     break;
    }
    
   }
   else//p在g右边
   {
    Node* u = g->_left;
    if (u && u->_color == RED)
    {
     u->_color = p->_color = BLACK;
     g->_color = RED;
     cur = g;
    }
    else
    {
     if (cur == p->_left)
     {
      RotateR(p);
      swap(cur, p);
     }

     RotateL(g);
     g->_color = RED;
     p->_color = BLACK;

     break;
    }
   }
   
  }
  //将根置为黑
  _header->_parent->_color = BLACK;
  //更新头的左右指针
  _header->_left = leftMost();
  _header->_right = rightMost();

  return true;
 }
-------------本文结束感谢您的阅读-------------