当前位置： 首页 > news >正文

【数据结构】基础：AVL树（平衡二叉树）

news 来源：原创 2024/4/19 11:44:30

【数据结构】基础：AVL树（平衡二叉树）

摘要：本文介绍二叉搜索树的改进AVL树（平衡二叉树），将对其概念与实现两部分展开。主要介绍其中的插入过程，其难点主要在于4个旋转过程。这个四个旋转过程，作者从几何特征，平衡因子特征出发，观察其变化情况与细节以及平衡因子的改变。最后进行性能分析的简要介绍。由于删除考察得比较少，因此本文并不对此进行介绍。

文章目录

  • 【数据结构】基础：AVL树（平衡二叉树）
    • 一、概述
    • 二、插入
      • 2.1 寻找插入位置
      • 2.2 更新平衡因子
      • 2.3 异常处理（旋转）
        • 2.3.1 右单旋(RotateR)
        • 2.3.2 左单旋(RotateL)
        • 2.3.3 左右双旋(RotateLR)
        • 2.3.4 右左双旋(RotateRL)
    • 三、验证
      • 3.1 验证搜索树
      • 3.2 验证其为平衡树
    • 四、性能分析
    • 五、完整代码

一、概述

二叉搜索树存在缺点，二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1（需要对树中的结点进行调整），即可降低树的高度，从而减少平均搜索长度。

平衡二叉树（AVL树）可以定义为或者是空树，或者是具有以下性质的二叉搜索树：

  • 它的左右子树都是AVL树
  • 左右子树高度之差（简称平衡因子）的绝对值不超过1（-1/0/1）

使用代码实现时，其定义如下：对于树的节点使用三叉链的方式，其中还包括对应的键值对，在此设计为包括平衡因子，便于后续的实现，代码示例如下：

template<class K,class V>
class AVLTreeNode{
public:
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;

	pair<K, V> _keyValue; // 键值对
	
	int _balanceFactor; // 平衡因子

	AVLTreeNode(const pair<K, V>& keyValue)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_keyValue(keyValue)
		,_balanceFactor(0)
	{}
};

template<class K,class V>
class AVLTree {
	typedef AVLTreeNode<K, V> AVLTreeNode;
private:
	AVLTreeNode* _root;
public:
	AVLTree()
		:_root(nullptr);
	{}
};

二、插入

AVL树的插入是在搜索二叉树的条件下进行改进，从而达到平衡的目的。因此主要基本思想可以分为：

  • 根据二叉搜索树的规则寻找插入位置
  • 调节对应的平衡因子，当平衡因子出现异常时，进行AVL树的修正

2.1 寻找插入位置

该步的方法与搜索二叉树的插入过程相似，首先找出键值对的键找出插入位置，其中记录parent和cur指针，便于在找到后简单的找出与父节点连接的方向以及完成插入节点的parent指针的连接。

if (_root == nullptr) {
    _root = new AVLTreeNode(kv);
    return true;
}
// 根据二叉搜索树的规则寻找插入位置
AVLTreeNode* parent = nullptr;
AVLTreeNode* cur = _root;
while (cur) {
    if (cur->_keyValue.first > kv.first) {
        parent = cur;
        cur = cur->_left;
    }
    else if (cur->_keyValue.first < kv.first) {
        parent = cur;
        cur = cur->_right;
    }
    else {
        return false;
    }
}
// 插入新节点
cur = new AVLTreeNode(kv);
if (parent->_keyValue.first > cur->_keyValue.first) {
    parent->_left = cur;
    cur->_parent = parent;
}
else {
    parent->_right = cur;
    cur->_parent = parent;
}

2.2 更新平衡因子

在插入完新节点后，需要对平衡因子进行更新，平衡因子的概念为：左右之树之差，当左子树高时为-1，右子树高时为1，相等为0，其他情况皆为异常状况。

插入新节点后，会影响到的节点，就是新插入节点的祖先们，因为新插入节点改变了这些祖先们子树的高度关系，因此可以通过parent指针来完成更新平衡因子的工作，规则如下：

  • 根据cur插入的位置，对于parent的平衡因子进行更新，当插入在parent的左子树时，balanceFactor需要减少，插入在右子树时需要增加balanceFactor

  • 更新以后，如果parent的平衡因子为0，更新结束。因为平衡因子更新前，parent树只有左子树或者只有右子树，插入新节点后，将空的一边填补，parent的高度不变，对于其祖先没有影响，图示如下：

  • 更新以后，如果parent的平衡因子为±1，说明插入前parent的平衡因子一定为0，插入后被更新成±1，此 时以parent为根的树的高度增加，需要继续向上更新

  • 更新以后，如果parent的平衡因子为±2，则parent的平衡因子违反平衡树的性质，需要对其进行旋转处理

过程代码如下：通过while循环以及parent的更新来完成对祖先的访问

// 更新平衡因子
while (parent){
    //根据cur插入的位置，对于parent的平衡因子进行更新，
    //当插入在parent的左子树时，balanceFactor需要减少，
    //插入在右子树时需要增加balanceFactor
    if (parent->_left == cur) {
        parent->_balanceFactor--;
    }
    else {
        parent->_balanceFactor++;
    }
    if (parent->_balanceFactor == 0) {
        break
    }
    // 继续往上更新
    else if (parent->_balanceFactor == 1 || parent->_balanceFactor == -1) {
        cur = parent;
        parent = parent->_parent;
    }
    else if (parent->_balanceFactor == 2 || parent->_balanceFactor == -2)
        // 对于AVL树平衡因子异常处理
    }
    else{
        // 说明插入更新平衡因子之前，树中平衡因子就有问题了
        assert(false);
    }
}

2.3 异常处理（旋转）

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

  • 新节点插入较高左子树的左侧：右单旋
  • 新节点插入较高右子树的右侧：左单旋
  • 新节点插入较高左子树的右侧：先左单旋再右单旋
  • 新节点插入较高右子树的左侧：先右单旋再左单旋

而这四种的旋转方式，需要符合两个规则分别为：保持搜索树的特性，并且控制平衡，以下对于这四种情况进行分别讲解：

2.3.1 右单旋(RotateR)

几何特征：当新节点插入较高左子树的左侧时，将其需要将其像右旋转，图示如下：

平衡因子特征：parent->_balanceFactor == -2 && cur->_balanceFactor == -1

修改平衡因子：cur->_balanceFactor = parent->_balanceFactor = 0;

旋转意义：将高度较高的子树的最大节点上提为根，将原来的根下移为子树的根，使得高度平衡。如此原来高度为H+2的子树降低为H+1，原来H的子树提高为H+1。

实现过程：

  • 从总体上观察，是将cur的右子树作为了parent的左子树，再将cur的右子树指向parent

    void RotateR(AVLTreeNode* parent) {
    AVLTreeNode* cur = parent->_left;
    AVLTreeNode* curR = cur->_right;

    parent->_left = curR;
    curR->_parent = parent;

    cur->_right = parent;
    parent->_parent = cur;
}

  • 对于整棵树的整体已经变化完毕了，但是还需要对树外的指针进行操作，即对于parent的parent也要进行连接。如果parent是根节点就不需要连接，将cur作为根，否则就需要找出链接的子树，并完成相互链接。

    void RotateR(AVLTreeNode* parent) {
    // cur一定存在 无需判断空
    AVLTreeNode* cur = parent->_left;
    AVLTreeNode* curR = cur->_right;
    // 对于parent的parent也要进行连接
    AVLTreeNode* parentParent = parent->_parent;

    parent->_left = curR;
	curR->_parent = parent;

    cur->_right = parent;
    parent->_parent = cur;
	// 如果parent是根节点就不需要连接，将cur作为根
    if (parent == _root) {
        _root = cur;
        _root->_parent == nullptr;
    }
    // 将cur作为根，否则就需要找出链接的子树，并完成相互链接
    else{
        if (parentParent->_left == parent) {
            parentParent->_left = cur;
            cur->_parent = parentParent;
        }
        else {
            parentParent->_right = cur;
            cur->_parent = parentParent;
        }
    }
}

  • 由于存在空指针的情况，因此需要对节点的子树进行判断

    void RotateR(AVLTreeNode* parent) {
    AVLTreeNode* cur = parent->_left;
    AVLTreeNode* curR = cur->_right;
    // 对于parent的parent也要进行连接
    AVLTreeNode* parentParent = parent->_parent;

    parent->_left = curR;
    // curR可能为空，因此需要对其进行空指针的判断
    if (curR != nullptr) {
        curR->_parent = parent;
    }
    cur->_right = parent;
    parent->_parent = cur;
	// 如果parent是根节点就不需要连接，将cur作为根
    if (parent == _root) {
        _root = cur;
        _root->_parent == nullptr;
    }
    // 将cur作为根，否则就需要找出链接的子树，并完成相互链接
    else{
        if (parentParent->_left == parent) {
            parentParent->_left = cur;
            cur->_parent = parentParent;
        }
        else {
            parentParent->_right = cur;
            cur->_parent = parentParent;
        }
    }
}

  • 最后对平衡因子进行相应的修改

    cur->_balanceFactor = parent->_balanceFactor = 0;

  • 完整代码

    void RotateR(AVLTreeNode* parent) {
    AVLTreeNode* cur = parent->_left;
    AVLTreeNode* curR = cur->_right;
    // 对于parent的parent也要进行连接
    AVLTreeNode* parentParent = parent->_parent;

    parent->_left = curR;
    // curR可能为空，因此需要对其进行空指针的判断
    if (curR != nullptr) {
        curR->_parent = parent;
    }
    cur->_right = parent;
    parent->_parent = cur;
	// 如果parent是根节点就不需要连接，将cur作为根
    if (parent == _root) {
        _root = cur;
        _root->_parent == nullptr;
    }
    // 将cur作为根，否则就需要找出链接的子树，并完成相互链接
    else{
        if (parentParent->_left == parent) {
            parentParent->_left = cur;
            cur->_parent = parentParent;
        }
        else {
            parentParent->_right = cur;
            cur->_parent = parentParent;
        }
    }
    cur->_balanceFactor = parent->_balanceFactor = 0;
}

2.3.2 左单旋(RotateL)

几何特征：当新节点插入较高右子树的右侧时，将其需要将其像左旋转，图示如下：

平衡因子特征：parent->_balanceFactor == 2 && cur->_balanceFactor == 1

修改平衡因子：cur->_balanceFactor = parent->_balanceFactor = 0;

旋转意义：将高度较高的子树的最大节点上提为根，将原来的根下移为子树的根，使得高度平衡。如此原来高度为H+2的子树降低为H+1，原来H的子树提高为H+1。

实现过程：与右单旋类似，只是方向不同，在此不做过多赘述

void RotateL(AVLTreeNode* parent) {
    AVLTreeNode* cur = parent->_right;
    AVLTreeNode* curL = cur->_left;

    AVLTreeNode* parentParent = parent->_parent;

    parent->_right = curL;
    if (curL != nullptr) {
        curR->_parent = parent;
    }

    parent->_parent = cur;
    cur->_left = parent;

    if (parent == _root) {
        _root = cur;
        _root->_parent = nullptr;
    }
    else {
        if (parentParent->_left == parent) {
            parentParent->_left = cur;
            cur->_parent = parentParent;
        }
        else {
            parentParent->_right = cur;
            cur->_parent = parentParent;
        }
    }

    cur->_balanceFactor = parent->_balanceFactor = 0;
}

2.3.3 左右双旋(RotateLR)

几何特征：新节点插入较高左子树的右侧，先左单旋再右单旋，图示如下：

在这里插入图片描述

平衡因子特征：parent->_balanceFactor == -2 && cur->_balanceFactor == 1

修改平衡因子：可以通过curR的balanceFactor来判断

  • bf == 0 ，H = 0时，表示插入节点为curR时，此时的平衡因子为皆为0

  • 当H ≠ 0时

    • 当bf == -1 时，cur->_balanceFactor = curR->_balanceFactor = 0以及parent->_balanceFactor = 1

    • 当bf == 1时，parent->_balanceFactor = curR->_balanceFactor = 0以及cur->_balanceFactor = -1

在这里插入图片描述

旋转意义：如果单纯的进行右旋转是无意义的，因为给予给原来根节点的左子树，与cur的左子树相比，旋转后仍然不符合AVL树的规则。为此，先通过左旋转来降低子树的高度，再进行右旋转进行第二次降低高度

实现过程：

  • 获取各个点的指针，便于旋转后进行对平衡因子的修改
  • 左单旋后右单旋
  • 平衡因子修改

完整代码：

void RotateLR(AVLTreeNode* parent) {
	AVLTreeNode* cur = parent->_left;
	AVLTreeNode* curR = cur->_right;
	int bf = curR->_balanceFactor;
	RotateL(cur);
	RotateR(parent);

	if (bf == 1) {
		parent->_balanceFactor = curR->_balanceFactor = 0;
		cur -> _balanceFactor = -1;
	}
	else if (bf == -1) {
		cur -> _balanceFactor = curR->_balanceFactor = 0;
		parent -> _balanceFactor = 1;
	}
	else if (bf == 0){
		cur -> _balanceFactor = curR->_balanceFactor = parent->_balanceFactor = 0;
	}
	else {
		assert(false);
	}
}

2.3.4 右左双旋(RotateRL)

几何特征：新节点插入较高右子树的左侧，先右单旋再左单旋

平衡因子特征：parent->_balanceFactor == 2 && cur->_balanceFactor == -1

修改平衡因子：与左右双旋的分析方法一致，此处不做赘述

  • bf == 0 ，H = 0时，表示插入节点为curR时，此时的平衡因子为皆为0
  • 当H ≠ 0时
    • 当bf == -1 时，parent->_balanceFactor = curR->_balanceFactor = 0以及cur->_balanceFactor = 1
    • 当bf == 1时，cur->_balanceFactor = curR->_balanceFactor = 0以及parent->_balanceFactor = -1

旋转意义：如果单纯的进行左旋转是无意义的，因为给予给原来根节点的右子树，与cur的右子树相比，旋转后仍然不符合AVL树的规则。为此，先通过右旋转来降低子树的高度，再进行左旋转进行第二次降低高度

实现过程：与左右双旋一致，不再赘述

完整代码：

void RotateRL(AVLTreeNode* parent) {
    AVLTreeNode* cur = parent->_right;
    AVLTreeNode* curR = cur->_left;
    int bf = curR->_balanceFactor;

    RotateR(cur);
    RotateL(parent);

    if (bf == -1) {
        parent->_balanceFactor = curR->_balanceFactor = 0;
        cur -> _balanceFactor = 1;
    }
    else if (bf == 1) {
        cur -> _balanceFactor = curR->_balanceFactor = 0;
        parent -> _balanceFactor = -1;
    }
    else if (bf == 0) {
        cur->_balanceFactor = curR->_balanceFactor = parent->_balanceFactor = 0;
    }
    else {
        assert(false);
    }
}

三、验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

  • 验证其为二叉搜索树
  • 验证其为平衡树

3.1 验证搜索树

中序遍历可得到一个有序的序列，就说明为二叉搜索树

public:
	void InOrder() {
		_InOrder(_root);
	}
private:
	void _InOrder(AVLTreeNode* root) {
		if (root == NULL)
			return;

		_InOrder(root->_left);
		cout << root->_keyValue.first << ":" << root->_keyValue.second << endl;
		_InOrder(root->_right);
	}

3.2 验证其为平衡树

每个节点子树高度差的绝对值不超过1，节点的平衡因子是否计算正确。通过递归法求出树的高度，当平衡因子不符合树的高度差或者平衡因子异常时返回false，代码如下：

private:
	bool _IsBalance(AVLTreeNode* root) {
		if (root == NULL)
			return true;

		// 对当前树进行检查
		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);

		if (rightHeight - leftHeight != root->_balanceFactor){
			return false;
		}

		return abs(rightHeight - leftHeight) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}
public:
	int Height(AVLTreeNode* root)
	{
		if (root == NULL)
			return 0;
		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}
	bool IsBalance()
	{
		return _IsBalance(_root);
	}

四、性能分析

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即log (N)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

五、完整代码

// AVLTree.h
#pragma once
#include <utility>
#include <iostream>
#include <assert.h>
using namespace std;
template<class K, class V>
class AVLTreeNode {
public:
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;

	pair<K, V> _keyValue; // 键值对

	int _balanceFactor; // 平衡因子

	AVLTreeNode(const pair<K, V>& keyValue)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _keyValue(keyValue)
		, _balanceFactor(0)
	{}
};

template<class K, class V>
class AVLTree {
	typedef AVLTreeNode<K, V> AVLTreeNode;
private:
	AVLTreeNode* _root;
private:
	void RotateR(AVLTreeNode* parent) {
		AVLTreeNode* cur = parent->_left;
		AVLTreeNode* curR = cur->_right;
		// 对于parent的parent也要进行连接
		AVLTreeNode* parentParent = parent->_parent;

		parent->_left = curR;
		// curR可能为空，因此需要对其进行空指针的判断
		if (curR != nullptr) {
			curR->_parent = parent;
		}

		cur->_right = parent;
		parent->_parent = cur;

		// 如果parent是根节点就不需要连接，将cur作为根
		if (parent == _root) {
			_root = cur;
			_root->_parent == nullptr;
		}
		// 将cur作为根，否则就需要找出链接的子树，并完成相互链接
		else {
			if (parentParent->_left == parent) {
				parentParent->_left = cur;
				cur->_parent = parentParent;
			}
			else {
				parentParent->_right = cur;
				cur->_parent = parentParent;
			}
		}
		// 平衡因子	
		cur->_balanceFactor = parent->_balanceFactor = 0;
	}
	void RotateL(AVLTreeNode* parent) {
		AVLTreeNode* cur = parent->_right;
		AVLTreeNode* curL = cur->_left;

		AVLTreeNode* parentParent = parent->_parent;

		parent->_right = curL;
		if (curL != nullptr) {
			curL->_parent = parent;
		}

		parent->_parent = cur;
		cur->_left = parent;

		if (parent == _root) {
			_root = cur;
			_root->_parent = nullptr;
		}
		else {
			if (parentParent->_left == parent) {
				parentParent->_left = cur;
				cur->_parent = parentParent;
			}
			else {
				parentParent->_right = cur;
				cur->_parent = parentParent;
			}
		}

		cur->_balanceFactor = parent->_balanceFactor = 0;
	}
	void RotateLR(AVLTreeNode* parent) {
		AVLTreeNode* cur = parent->_left;
		AVLTreeNode* curR = cur->_right;
		int bf = curR->_balanceFactor;
		RotateL(cur);
		RotateR(parent);

		if (bf == 1) {
			parent->_balanceFactor = curR->_balanceFactor = 0;
			cur -> _balanceFactor = -1;
		}
		else if (bf == -1) {
			cur -> _balanceFactor = curR->_balanceFactor = 0;
			parent -> _balanceFactor = 1;
		}
		else if (bf == 0){
			cur -> _balanceFactor = curR->_balanceFactor = parent->_balanceFactor = 0;
		}
		else {
			assert(false);
		}
	}
	void RotateRL(AVLTreeNode* parent) {
		AVLTreeNode* cur = parent->_right;
		AVLTreeNode* curR = cur->_left;
		int bf = curR->_balanceFactor;

		RotateR(cur);
		RotateL(parent);

		if (bf == -1) {
			parent->_balanceFactor = curR->_balanceFactor = 0;
			cur -> _balanceFactor = 1;
		}
		else if (bf == 1) {
			cur -> _balanceFactor = curR->_balanceFactor = 0;
			parent -> _balanceFactor = -1;
		}
		else if (bf == 0) {
			cur->_balanceFactor = curR->_balanceFactor = parent->_balanceFactor = 0;
		}
		else {
			assert(false);
		}
	}
	void _InOrder(AVLTreeNode* root) {
		if (root == NULL)
			return;

		_InOrder(root->_left);
		cout << root->_keyValue.first << ":" << root->_keyValue.second << endl;
		_InOrder(root->_right);
	}
	bool _IsBalance(AVLTreeNode* root) {
		if (root == NULL)
			return true;

		// 对当前树进行检查
		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);

		if (rightHeight - leftHeight != root->_balanceFactor){
			//cout << "发生错误：";
			//cout << root->_keyValue.first << " 的平衡因子是:" << root->_balanceFactor 
			//	<< " 应该是:" << rightHeight - leftHeight << endl;
			return false;
		}

		return abs(rightHeight - leftHeight) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}
public:
	AVLTree()
		:_root(nullptr)
	{}
	bool Insert(const pair<K, V>& kv) {
		if (_root == nullptr) {
			_root = new AVLTreeNode(kv);
			return true;
		}
		// 根据二叉搜索树的规则寻找插入位置
		AVLTreeNode* parent = nullptr;
		AVLTreeNode* cur = _root;
		while (cur) {
			if (cur->_keyValue.first > kv.first) {
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_keyValue.first < kv.first) {
				parent = cur;
				cur = cur->_right;
			}
			else {
				return false;
			}
		}
		// 插入新节点
		cur = new AVLTreeNode(kv);
		if (parent->_keyValue.first > cur->_keyValue.first) {
			parent->_left = cur;
			cur->_parent = parent;
		}
		else {
			parent->_right = cur;
			cur->_parent = parent;
		}
		// 更新平衡因子
		while (parent) {
			//根据cur插入的位置，对于parent的平衡因子进行更新，
			//当插入在parent的左子树时，balanceFactor需要减少，
			//插入在右子树时需要增加balanceFactor
			if (parent->_left == cur) {
				parent->_balanceFactor--;
			}
			else {
				parent->_balanceFactor++;
			}
			if (parent->_balanceFactor == 0) {
				break;
			}
			// 继续往上更新
			else if (parent->_balanceFactor == 1 || parent->_balanceFactor == -1) {
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_balanceFactor == 2 || parent->_balanceFactor == -2) {
				// 对于AVL树平衡因子异常处理
				if (parent->_balanceFactor == -2 && cur->_balanceFactor == -1) {
					RotateR(parent);
				}
				else if (parent->_balanceFactor == 2 && cur->_balanceFactor == 1) {
					RotateL(parent);
				}
				else if (parent->_balanceFactor == -2 && cur->_balanceFactor == 1) {
					RotateLR(parent);
				}
				else if (parent->_balanceFactor == 2 && cur->_balanceFactor == -1) {
					RotateRL(parent);
				}
				else {
					assert(false);
				}
				break;
			}
			else {
				// 说明插入更新平衡因子之前，树中平衡因子就有问题了
				assert(false);
			}
		}
		return true;
	}
	void InOrder() {
		_InOrder(_root);
	}
	int Height(AVLTreeNode* root)
	{
		if (root == NULL)
			return 0;
		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);
		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}
	bool IsBalance()
	{
		return _IsBalance(_root);
	}
};

补充：

  1. 代码将会放到：C++/C/数据结构代码链接 ，欢迎查看！
  2. 欢迎各位点赞、评论、收藏与关注，大家的支持是我更新的动力，我会继续不断地分享更多的知识！

相关文章：

  • 【C++11】lambda表达式、包装器、bind 与 placeholders
  • 【深度学习基础6】自编码器及其变体
  • 数学知识-约数
  • 【Python模块】psutil
  • 配置安全的linux-apache服务器（5）
  • 【栈】数据结构栈的实现
  • BPMP 需求
  • 软件测试（概念Ⅰ） · 软件测试的基本概念 · 什么是需求 · 测试用例的概念 · 软件错误(bug)的概念
  • 理论一：当谈论面向对象的时候，我们到底在谈论什么？
  • 带你三分种了解网络用语之网络层、传输层
  • 元宵节：css画灯笼
  • 异步编程实践
  • Go XORM学习
  • 【golang/go语言】go语言中包的使用、Init()函数、协程和接口
  • 【电源专题】JEITA学习
  • cadence SPB17.4 S032 - PSpice - 仿真元件参数的含义 - 以VSIN为例
  • 印刷线路板焊盘和金手指自动光学检测研究
  • 算法刷题打卡第81天：兼具大小写的最好英文字母
  • 【MySQL】MyCAT三大配置文件详解（MySQL专栏启动）
  • go-zero源码阅读-布隆过滤器
  • 电加热油锅炉工作原理_电加热导油
  • 大型电蒸汽锅炉_工业电阻炉
  • 燃气蒸汽锅炉的分类_大连生物质蒸汽锅炉
  • 天津市维修锅炉_锅炉汽化处理方法
  • 蒸汽汽锅炉厂家_延安锅炉厂家
  • 山西热水锅炉厂家_酒店热水 锅炉
  • 蒸汽锅炉生产厂家_燃油蒸汽发生器
  • 燃煤锅炉烧热水_张家口 淘汰取缔燃煤锅炉
  • 生物质锅炉_炉
  • 锅炉天然气_天燃气热风炉