C++中高阶数据结构(AVL树的原理讲解)

AVL树

AVL树的定义

avl本质是搜索树,是高度平衡二叉搜索树.特点是:任何树的左右子树的高度差不超过1.最大的高度差值最大也只能是1,也称之为平衡因子,

平衡因子就是右子树减去左子树的值,这个值的绝对值的最大值只能是1.这个平衡因子不是必须的,只是一种控制方式,方便我们更便捷的控制树.

节点的定义

struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf; // balance factor
	pair<K, V> _kv;
	AVLTreeNode(const pair<K,V> kv)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
		, _kv(kv)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

向AVL树插入节点

• 先按着搜索树的规则插入节点
• 接着利用平衡因子来观测该树是否还是AVL树
  • 新插入的节点可能会影响该节点的部分祖先的平衡因子的值.
  • 更新规则:在c的左边新增,那么p->bf–,在c的右边新增,那么p->bf++,那么是否还会继续影响祖先呢?取决于p的高度是否变化.
  • 更新之后:父亲的 平衡因子如果是0的话,那么p所在的子树的高度不变不会影响爷爷.(如果p的平衡因子更新之后是0,就说明过更新之前是1或者是-1,说明是在矮的那一边插入了节点,p的高度不变,不会影响爷爷.),此时更新结束
  • 更新之后p的平衡因子是1或者是-1,那么p所在的子树的高度变了.会影响爷爷,说明更新之前p->bf是0,在p的有一边插入之后,p的高度变化了,就会影响爷爷.
  • 更新之后p的平衡因子成了2或者是-2,此时p所在子树就不是AVL树了,那么就需要进行旋转处理了.
  • 最后c成了根节点之后,那么就是更新条件结束了
• 三种结束条件:
  • 更新到root结束,p->bf==0结束,旋转让parent所在子树的高度回到了插入之前,不会对上层的bf有影响,结束.

代码实现:

bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		while (parent)
		{
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				// 旋转处理
				if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}
				else
				{
					RotateRL(parent);
				}

				break;
			}
			else
			{
				// 插入之前AVL树就有问题
				assert(false);
			}
		}

		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
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

AVL中的旋转处理

根据插入数据的不同情况可以分为四种情况的

左单旋

当碰到如下图的情况:(红色的是插入节点之后节点对应的平衡因子的值,红色的方块代表插入了一个节点)

当c的右边增加了节点导致了p的平衡因子变成了2之后,此时将subR的左子树连接到parent的右子树上,紧接着将整个parent为根,a为左子树,b为右子树的整棵树连接到subR的左边.此时再计算平衡因子,发现都成了0,整棵树就满足了avl树的规则.

这里subR在插入节点之前,b子树和c子树的高度一定是相同的(高度也可以是0),只有如此,subR的节点的平衡因子才是0,假如b子树和c子树的高度不同,那么subR的平衡因子是值可能是1或者是-1,此时在subR的右边插入节点,subR节点的平衡因子可能会变成0或者是2,若变成0,avl树的更新就结束了,根本就不需要调整,若变成了2,那么需要调整的树就是subR这颗树,而不是parent这个树.

同理,a子树的节点的高度也一定是h

• 如果a子树的高度是h+1,那么parent的平衡因子就是0了,此时无论是在parent的左边还是右边插入元素,都无法使parent的平衡因子更新成2或者是-2
• 如果a子树的高度使h-1,那么此时这颗树根本就不是AVL树了,说明在新节点插入之前就不是AVL树

代码实现:

void RotateL(Node* parent)
{
	Node* subR = parent->_left;
    Node* subRL = subR->_right;
	Node* ppnode = parent->_parent;
    
    
    parent->_right = subRL;
    if(subRL) // subRL的高度可能是0
    subRL->_parent = parent;
    
    subR->_left = parent;
    parent->_parent = subR;
    
    // 假如插入节点之前parent就是整棵树的根
	if(ppnode == nullptr)
    {
        _root = subR;
        subR->_parent = nullptr;
    }
    else
    {
        if(ppnode->_left == parent)
        {
            ppnode->_left = subR;
        }
        else
        {
            ppnode->_right = subR;
        }
        subR->_parent = ppnode;
    }
    parent->_bf =0;
    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
30
31
32
33
34
35

右单旋

当遇到如下图的情况时:(红色是更新之后的平衡因子的值):

新节点插入到较高左子树的左侧,就使用右单旋.因为此时的树看上去就是整个左侧高,右侧低的形式

右单旋的方法:将subL的b这个右子树连接到parent的左边,紧接着,以parent为根,b为左子树,c为右子树的整棵树连接到subL的右边.

代码实现:

void RotateR(Node* parent)
{
	Node* subL = parent->_left;
    Node* subLR = subL->_right;
    Node* grandParent = parent->_parent;
    
    parent->_left = subLR;
    // 同理,subLR的高度可能是0 
    if(subLR)
    subLR->_parent = parent;
    
    subL->_right = parent;
    parent->_parent = subL;
    
    // 假如插入节点之前parent就是整棵树的根
    if(_root == parent)
    {
        _root = subL;
        subL->_parent = nullptr;
    }
    else
    {
        if(grandParent->_left ==  parent)
        {
            grandParent->_left = subL;
        }
        else
        {
            grandParent->_right = subL;
		}
        subL->_parent = grandParent;
    }
    parent->_bf =0;
    subL->_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
30
31
32
33
34
35

左右双旋

当新的节点插入在较高左树的右边时,需要进行左右双旋.

假定是如下图的情况:

此时在h这个子树插入数据时,整棵树的左边是较高的,此时我们假如采用右旋转,则会:

会发现,右旋之后,值为30的节点的平衡因子还是-2,所以我们不能采用单旋了,使用双旋.

• 假设h是大于0的情况:

  先将b子树拆分:
  

  将b拆分为值为40(这里40只是例子,只要满足时大于30小于60即可)的节点和e子树和f子树,那么此时由e和f两个子树了,新的节点就会有两种选择了.

  • 当在e子树插入数据时:以30为断点进行左单旋,接着对整棵树进行右单旋
    

    通过图可知,最后形成的树是符合要求的,并且各自的平衡因子经过计算都是满足要求的.

  • 当在f子树插入节点时:
    对仍然对局部进行左单旋,接着对整棵树进行右单旋.

    

    并且经过计算之后的平衡因子经过计算之后也是符合要求的.

  当h==0时:
  此时e和f就不存在了,

  • 当在30的右边插入节点时,就先对30为根的树进行做单旋,对整棵树进行右单旋.如下图所示,最终计算出的平衡因子都是符合要求的.

  

  • 当在30的左边插入节点时:可以直接对整棵树进行右单旋即可.

  最终形成的树的关键节点的平衡因子的如何确定:由上图可以看出规律

  • 当h!=0时
    • 当新节点在e子树插入时:40所在节点的平衡因子是0,30所在节点的平衡因子是0,60所在节点的平衡因子是1.
    • 当新节点在f子树插入时:40所在节点的平衡因子是0,30所在节点的平衡因子是-1,60所在节点的平衡因子是0.
  • 当h==0时,这个三个关键节点的平衡因子都是0

  如何确定规律呢?

  因为e和f这两颗子树的高度是相同的.所以在e树插入数据时,e的parent的平衡因子就会更新为-1,
  

  当是在f树插入节点时,f的parent的平衡因子就会更新成1.
  

  当e和f不存在时:
  

  代码实现:

  可以就可以利用subL的右节点的平衡因子的值来确定关键节点的平衡因子的值

  这里可以复用前面的代码,但是前面的左旋和右旋都会将节点的平衡因子都改成0.所以需要提前保存这个值

  void RotateLR(Node* parent)
  {
  	// 记录节点,为了保存节点里的_bf的值.
      Node* subL = parent->_left;
  	Node* subLR = subL->_right;
     
      // 提前保存好平衡因子,防止被修改
      int bf = subLR->_bf;
      // 直接调用
      RotateL(parent->_left);
      RotateR(parent);
      
  	if(bf == -1)
      {
          subLR->bf = 0;
          subL->_bf = 0;
          parent->_bf = 1;
      }
      else if(bf == 1)
      {
          subLR->_bf = 0;
         	subL->_bf = -1;
          parent->_bf = 0;
      }
      else if(bf == 0)
      {
  		subLR->_bf = 0;
         	subL->_bf = 0;
          parent->_bf = 0;
      }
      else
      {
          // 此时就不是AVL树. ![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/3a4298086b6f436385586435bd9eaad7.png)
  
          assert(false);  
      }
  }
  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

右左双旋

当新节点插入在较高右树的左侧时,需要右左双旋了.采用的是和左右双旋类似的思想

• 当h!=0时

  • 当在e树插入时:
    

  • 当在f树插入时:
    

• 当h==0时
  

代码实现:

void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	
	int bf = subRL ->_bf;
	
	RotateR(parent->_right);
	RotateL(parent);

	if(bf == -1)
	{
		subRL ->_bf = 0;
		parent->_bf =0;
		subR ->_bf = 1;
	}
	else if(bf == 1)
	{
		subRL->_bf = 0;
		parent->_bf =-1;
		subR->_bf = 0;
	}
	else if(bf ==0)
	{
		subRL->_bf = 0;
		parent->_bf =0;
		subR->_bf = 0;
	}
	else
	{
		assert(false);
	}
}
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

如何验证一个树是否是avl树

可以计算每一个子树的高度,观察高度差.

可以先写一个检查高度的函数

int _Height(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}
	int Height()
	{
		return _Height(_root);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

在写一个Isbalance函数检查函数的左右高度是否符合要求

bool _IsBalance(Node* root)
	{
		if (root == nullptr)
			return true;

		int balance = _Height(root->_right) - _Height(root->_left);

		if (abs(balance) <= 2)
		{
			cout << "平衡" << endl;
			return true;
		}
		else
		{
			cout << "不平衡" << endl;
			return false;
		}
		if (balance != root->_bf)
		{
			cout << " 平衡因子异常 ";
			return false;
		}

		return _IsBalance(root->_left) && _IsBalance(root->_right);
	}
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

但是这个函数使用的递归太多了,复杂度太高了.每次在计算高度差的时候,已经将高度给计算出来了,但是函数的最后还是要计算左右子树的高度.

balance的优化,使用一个引用来记录height的左右高度.

bool _IsBalance(Node* root,int& Height)
	{
		if (root == nullptr)
        {
            height = 0;
            return true;            
        }
			

		int balance = _Height(root->_right) - _Height(root->_left);
		int leftHeight = 0,rightHeight = 0;
    // 左右子树只要有一个不是平衡树,就返回false
    	if (!_IsBalance(root->_left, leftHeight) || !_IsBalance(root->_right, rightHeight))
		{
			return false;
		}
		if (abs(rightHeight - leftHeight) >= 2)
		{
			cout <<root->_kv.first<<"不平衡" << endl;
			return false;
		}
		if (balance != root->_bf)
		{
			cout << " 平衡因子异常 ";
			return false;
		}
		height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    	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

结束

关于AVL树的讲解就到这里啦,如有不足,请在评论区指正,下期见!