首页 > 电脑手机

平衡二叉树——AVl树

电脑手机 2024-11-25 23:15:01 854

AVL树

  • AVl树的概念
  • AVL树的实现
    • AVL树的结构
    • AVl树的插入
    • AVL树的旋转
      • 左单旋
      • 右单旋
      • 左右双旋
      • 右左双旋
    • AVl树以高度递归实现完整代码

平衡二叉树——AVl树

AVl树的概念

AVL树是一种自平衡的二叉搜索树（Binary Search Tree, BST），由两位苏联数学家 Georgy Adelson-Velsky 和 Evgenii Landis 于 1962 年提出。其主要特点是通过保持树的平衡来保证基本操作（插入、删除和查找）的时间复杂度在 O(log n) 范围内。

概念

二叉搜索树：

AVL树是一种二叉搜索树，意味着每个节点都有一个键值，左子树的所有节点值小于该节点的值，右子树的所有节点值大于该节点的值。

平衡因子：

AVL树的每个节点都有一个平衡因子（Balance Factor），定义为该节点左子树的高度减去右子树的高度。
平衡因子可以取值为 -1、0 或 1。具体定义如下：
BF(node) = height(left subtree) - height(right subtree)
只有当平衡因子的绝对值不超过 1 时，树才是平衡的。

性质

自平衡：

AVL树在插入或删除节点时，通过旋转操作来保持树的平衡，以确保所有基本操作的时间复杂度为 O(log n)。

高度限制：

AVL树的高度 h 和节点数 n 之间存在关系：h ≤ 1.44 * log2(n + 2)。
这表明 AVL树相较于普通二叉搜索树，在最坏情况下也能保持较低的高度。

旋转操作：

当树失去平衡时，可以通过以下四种旋转操作来恢复平衡：

  • 单右旋（Right Rotation）
  • 单左旋（Left Rotation）
  • 左右旋（Left-Right Rotation）
  • 右左旋（Right-Left Rotation）

查找、插入与删除操作：

查找操作的时间复杂度为 O(log n)，因为 AVL树保持了平衡性。
插入和删除节点后，需要检查每个祖先节点的平衡因子，并可能进行旋转以恢复树的平衡。

应用
AVL树适合用于需要频繁插入和删除操作的场景，例如数据库管理系统和内存管理等，因为它能够提供快速的查找、插入和删除操作。由于AVL树总是保持平衡，因此在处理大量数据时，性能表现优越。

AVL树的实现

AVL树的结构

template<class T>
struct AVLTreeNode  //节点模板
{
	AVLTreeNode(const T& data = T())
		: _pLeft(nullptr)
		, _pRight(nullptr)
		, _pParent(nullptr)
		, _data(data)
		, _bf(0)
	{}

	AVLTreeNode<T>* _pLeft;  //左孩子
	AVLTreeNode<T>* _pRight;  //右孩子
	AVLTreeNode<T>* _pParent;  //父节点
	T _data;   //数据
	int _bf;   // 节点的平衡因子
};

template<class K, class V>
class AVLTree  //AVL树模板
{
typedef AVLTreeNode<K, V> Node;   //减少繁琐的写法
public:
//...函数操作——插入，左旋等
private:
Node* _pRoot = nullptr;
};

以模板类实现AVl树，可以自由套用各种类型的数据，父节点指针方便向上查找，检查平衡因子，方便旋转。

AVl树的插入

AVL树的插入流程包括以下几个步骤：

  1. 插入节点
    首先，按照普通二叉搜索树（BST）的规则将新节点插入到树中。这意味着：
    如果新节点的值小于当前节点的值，则继续向左子树插入。
    如果新节点的值大于当前节点的值，则继续向右子树插入。

  2. 更新高度
    在插入新节点后，更新每个节点的高度。节点的高度是其左子树和右子树高度的最大值加一。

  3. 计算平衡因子
    从插入节点的父节点开始，逐级向上检查每个祖先节点的平衡因子（Balance Factor, BF），即左子树高度减去右子树高度（BF = height(left) - height(right)），或者相反。

4.检查平衡
如果某个节点的平衡因子的绝对值超过 1（即 BF < -1 或 BF > 1），则该节点失去了平衡，需要进行旋转操作来恢复平衡。

更新原则：

  • 平衡因⼦ = 右⼦树⾼度 - 左⼦树⾼度
  • 只有⼦树⾼度变化才会影响当前结点平衡因⼦。
  • 插⼊结点，会增加⾼度，所以新增结点在parent的右⼦树，parent的平衡因⼦++，新增结点在parent的左⼦树，parent平衡因⼦–
  • parent所在⼦树的⾼度是否变化决定了是否会继续往上更新

更新停⽌条件：

  • 更新后parent的平衡因⼦等于0，更新中parent的平衡因⼦变化为-1->0或者1->0，说明更新前
    parent⼦树⼀边⾼⼀边低，新增的结点插⼊在低的那边，插⼊后parent所在的⼦树⾼度不变，不会
    影响parent的⽗亲结点的平衡因⼦，更新结束。
  • 更新后parent的平衡因⼦等于1或-1，更新前更新中parent的平衡因⼦变化为0->1或者0->-1，说明更新前parent⼦树两边⼀样⾼，新增的插⼊结点后，parent所在的⼦树⼀边⾼⼀边低，parent所在的⼦树符合平衡要求，但是⾼度增加了1，会影响arent的⽗亲结点的平衡因⼦，所以要继续向上更新。
  • 更新后parent的平衡因⼦等于2或-2，更新前更新中parent的平衡因⼦变化为1->2或者-1->-2，说明更新前parent⼦树⼀边⾼⼀边低，新增的插⼊结点在⾼的那边，parent所在的⼦树⾼的那边更⾼了，破坏了平衡，parent所在的⼦树不符合平衡要求，需要旋转处理，旋转的⽬标有两个：
  • 1、把parent⼦树旋转平衡。
  • 2、降低parent⼦树的⾼度，恢复到插⼊结点以前的⾼度。所以旋转后也不需要继续往上更新，插⼊结束。
  1. 选择旋转方式
    根据失衡节点的子树结构，选择适当的旋转方式：

左左情况（Left-Left Case）：

当新节点被插入到左子树的左侧时，执行单右旋。
右右情况（Right-Right Case）：

当新节点被插入到右子树的右侧时，执行单左旋。
左右情况（Left-Right Case）：

当新节点被插入到左子树的右侧时，先对左子树进行左旋，然后对当前节点进行右旋。
右左情况（Right-Left Case）：

当新节点被插入到右子树的左侧时，先对右子树进行右旋，然后对当前节点进行左旋。

  1. 旋转操作
    进行相应的旋转操作来恢复树的平衡。旋转操作的基本步骤如下：
    在旋转过程中调整节点的指针，以确保树的结构保持正确。

  2. 完成插入
    完成上述步骤后，AVL树就会保持自平衡状态，所有基本操作的时间复杂度仍然是 O(log n)。

代码实现：

bool Insert(const T& data)
{
	Node* node = new Node(data);

	if (_pRoot == nullptr)
	{
		_pRoot = node;
		return true;
	}

	Node* cur = _pRoot;
	Node* par = nullptr;
	while (cur)
	{
		par = cur;
		if (cur->_data > data)
		{
			cur = cur->_pLeft;
		}
		else if(cur->_data < data)
		{
			cur = cur->_pRight;
		}
		else
		{
			delete node;
			return false;
		}
	}

	//平衡因子 = 右 - 左
	if (par->_data > data)
	{
		par->_pLeft = node;
	}
	else
	{
		par->_pRight = node;
	}
	cur = node;
	cur->_pParent = par;

	while (par)
	{
		if (par->_pLeft == cur)
		{
			par->_bf--;
		}
		else
		{
			par->_bf++;
		}

		if (par->_bf == 0) break;

		if (par->_bf == 1 || par->_bf == -1)
		{
			cur = par;
			par = par->_pParent;
		}
		else if (par->_bf == 2 && cur->_bf == 1)
		{
			//左单旋
			RotateL(par);
			break;
		}
		else if (par->_bf == 2 && cur->_bf == -1)
		{
			//左右双旋
			RotateLR(par);
			break;
		}
		else if (par->_bf == -2 && cur->_bf == -1)
		{
			//右单旋
			RotateR(par);
			break;
		}
		else if(par->_bf == -2 && cur->_bf == 1)
		{
			//右左双旋
			RotateRL(par);
			break;
		}
		else
		{
			assert(false);
		}


	}

	return true;
}

AVL树的旋转

平衡因子：右子树高度 - 左子树高度

左单旋

如下是最简单的一种左单旋的情况，

左单旋之后如图：

代码实现：

void LeftRotate(Node* par)
{
	//右孩子
	Node* rchild = par->_pRight;
	//父节点的父亲
	Node* ppar = par->_pParent;

	//旋转操作
	//右孩子的左孩子改成父节点
	rchild->_pLeft = par;
	
	//父节点的父亲改为左孩子
	par->_pParent = rchild;
	//右孩子的父亲改为父节点的父亲
	rchild->_pParent = ppar;

	//改变平衡因子
	par->_bf = 0;
	rchild->_bf = 0;

}

有子节点的复杂左单旋的情况：

左单旋之后：

这种情况下需要多处理一个右孩子的左节点，将其接到父节点的右孩子上，保持二叉搜索树的性质。

实现代码：

void LeftRotate(Node* par)
{
	//右孩子
	Node* rchild = par->_pRight;
	//父节点的父亲
	Node* ppar = par->_pParent;

	//**右孩子的左孩子**
	Node* rlchild = rchild->_pLeft;

	//旋转操作
	//右孩子的左孩子改成父节点
	rchild->_pLeft = par;

	//**父节点的右孩子变成原本右孩子的左孩子**
	par->_pRight = rlchild;
	
	//父节点的父亲改为右孩子
	par->_pParent = rchild;
	//左孩子的父亲改为父节点的父亲
	rchild->_pParent = ppar;

	//**如果右左孩子存在，其父节点需要改变为原本的父节点**
	if (rlchild)
		rlchild->_pParent = par;

	//改变平衡因子
	par->_bf = 0;
	rchild->_bf = 0;

}

除此之外，还要考虑父节点为根节点的情况下，需要改变根节点的指针。如果不是，要判断父节点的父亲的情况，将父节点的父亲的孩子指针指向更改后的新的子树父节点

最终代码：

void LeftRotate(Node* par)
{
	//右孩子
	Node* rchild = par->_pRight;
	//父节点的父亲
	Node* ppar = par->_pParent;

	//**右孩子的左孩子**
	Node* rlchild = rchild->_pLeft;

	//旋转操作
	//右孩子的左孩子改成父节点
	rchild->_pLeft = par;

	//**父节点的右孩子变成原本右孩子的左孩子**
	par->_pRight = rlchild;
	
	//父节点的父亲改为右孩子
	par->_pParent = rchild;
	//左孩子的父亲改为父节点的父亲
	rchild->_pParent = ppar;

	//**如果右左孩子存在，其父节点需要改变为原本的父节点**
	if (rlchild)
		rlchild->_pParent = par;

	//改变平衡因子
	par->_bf = 0;
	rchild->_bf = 0;

	if (par == _pRoot)
	{
		//如果父节点为根节点，更改根节点的指向
		_pRoot = rchild;
	}
	else
	{
		//判断原本的父节点是父节点父亲的左孩子还是右孩子
		if (ppar->_pLeft == par)
		{
			ppar->_pLeft = rchild;
		}
		else
		{
			ppar->_pRight = rchild;
		}
	}
}

右单旋

右单旋的情况和左单旋基本一致，只是反向了，是镜像操作，不多赘述了。

简单的右单旋的情况：

右单旋的情况后：

最终代码：

void RightRotate(Node* par)
{
	//左孩子
	Node* lchild = par->_pLeft;
	//父节点的父亲
	Node* ppar = par->_pParent;

	//**左孩子的右孩子**
	Node* lrchild = lchild->_pRight;

	//旋转操作
	//左孩子的右孩子改成父节点
	lchild->_pRight = par;

	//**父节点的左孩子变成原本左孩子的右孩子**
	par->_pLeft = lrchild;

	//父节点的父亲改为右孩子
	par->_pParent = rchild;
	//左孩子的父亲改为父节点的父亲
	lchild->_pParent = ppar;

	//**如果左右孩子存在，其父节点需要改变为原本的父节点**
	if (lrchild)
		lrchild->_pParent = par;

	//改变平衡因子
	par->_bf = 0;
	lchild->_bf = 0;

	if (par == _pRoot)
	{
		//如果父节点为根节点，更改根节点的指向
		_pRoot = rchild;
	}
	else
	{
		//判断原本的父节点是父节点父亲的左孩子还是右孩子
		if (ppar->_pLeft == par)
		{
			ppar->_pLeft = lchild;
		}
		else
		{
			ppar->_pRight = lchild;
		}
	}
}

左右双旋

左右双旋的情况如下：

这种情况下就不能只进行右旋了，单纯右旋会变成这样：

情况并没有改变，只是变了个方向，所以需要先对左孩子进行左旋，然后对整体右旋：

左孩子左旋：

整体右旋：


旋转之后改变平衡因子，根据是否有孩子分类讨论平衡因子的改变，下面会进行分类：

实现代码：

void LeftRightRotate(Node* par)
{
	//左孩子
	Node* lchild = par->_pLeft;
	//左孩子的右孩子
	Node* lrchild = lchild->_pRight;
	//父节点的父亲
	Node* ppar = par->_pParent;

	LeftRotate(lchild);
	RightRotate(par);

	//平衡因子改变...........

}

情况一：

当前情况下，lrchild的bf平衡因子为0，结果为三个节点的平衡因子都为0，代码为：

void LeftRightRotate(Node* par)
{
	//左孩子
	Node* lchild = par->_pLeft;
	//左孩子的右孩子
	Node* lrchild = lchild->_pRight;
	//父节点的父亲
	Node* ppar = par->_pParent;

	LeftRotate(lchild);
	RightRotate(par);

	if (lrchild->_bf == 0)
	{
		par->_bf = 0;
		lchild->_bf = 0;
		lrchild->_bf = 0;
	}
	else if (lrchild->_bf == -1)
	{
	
	}
	else if (lrchild->_bf == 1)
	{
	
	}
	else
	{
		assert(flase);
	}

}

情况二：

此情况下lrchild的BF = -1， 旋转后结果如图，代码如下：

void LeftRightRotate(Node* par)
{
	//左孩子
	Node* lchild = par->_pLeft;
	//左孩子的右孩子
	Node* lrchild = lchild->_pRight;
	//父节点的父亲
	Node* ppar = par->_pParent;

	LeftRotate(lchild);
	RightRotate(par);

	if (lrchild->_bf == 0)
	{
		par->_bf = 0;
		lchild->_bf = 0;
		lrchild->_bf = 0;
	}
	else if (lrchild->_bf == -1)
	{
		par->_bf = 1;
		lchild->_bf = 0;
		lrchild->_bf = 0;
	}
	else if (lrchild->_bf == 1)
	{

	}
	else
	{
		assert(flase);
	}

}

情况三：


此情况下lrchild的BF = 1， 旋转后结果如图，代码如下：

void LeftRightRotate(Node* par)
{
	//左孩子
	Node* lchild = par->_pLeft;
	//左孩子的右孩子
	Node* lrchild = lchild->_pRight;
	//父节点的父亲
	Node* ppar = par->_pParent;

	LeftRotate(lchild);
	RightRotate(par);

	if (lrchild->_bf == 0)
	{
		par->_bf = 0;
		lchild->_bf = 0;
		lrchild->_bf = 0;
	}
	else if (lrchild->_bf == -1)
	{
		par->_bf = 1;
		lchild->_bf = 0;
		lrchild->_bf = 0;
	}
	else if (lrchild->_bf == 1)
	{
		par->_bf = 0;
		lchild->_bf = -1;
		lrchild->_bf = 0;
	}
	else
	{
		assert(flase);
	}

}

右左双旋

右左双旋类似与上，最终代码如下：

void RightLeftRotate(Node* par)
{
	Node* ppar = par->_pParent;
	Node* rchild = par->_pRight;
	Node* rlchile = rchild->_pLeft;
	
	RotateR(par->_pRight);
	RotateL(par);
	
	int bf = rlchile->_bf;
	
	if (bf == 0)
	{
		par->_bf = 0;
		rchild->_bf = 0;
		rlchile->_bf = 0;
	}
	else if (bf == -1)
	{
		par->_bf = 0;
		rchild->_bf = 1;
		rlchile->_bf = 0;
	}
	else if (bf == 1)
	{
		par->_bf = -1;
		rchild->_bf = 0;
		rlchile->_bf = 0;
	}
	else
	{
		assert(false);
	}

}

余下的查找查找，删除等雷同与二叉搜索树，只是在此基础上加入旋转操作，不在赘述。

AVl树以高度递归实现完整代码

typedef struct Treenode
{
	int data;
	struct Treenode* left;
	struct Treenode* right;
	int height;
}node;



node* BuyNode(int x)
{
    Treenode* newnode = new node;
    if (newnode == nullptr)
    {
        perror("New node:");
        exit(-1);
    }
       
    newnode->data = x;
    newnode->height = 1;
    newnode->left = nullptr;
    newnode->right = nullptr;
    return newnode;
}

int GetAVLheight(node* n)
{
    if(n == nullptr)
        return 0;

    return n->height;
}

int GetBalance(node* root)
{
    if(root == nullptr)
        return 0;

    return GetAVLheight(root->left) - GetAVLheight(root->right);
}

void updataHeight(node* root)
{
    root->height = max(GetAVLheight(root->left), GetAVLheight(root->right)) + 1;
}

void PreOrder(node* root)
{
    if (root == nullptr)
    {
        cout << " null";
        return;
    }

    cout << " " << root->data;
    PreOrder(root->left);
    PreOrder(root->right);
}

void DestroyAVLTree(node* root)
{
    if (root == nullptr)
    {
        return;
    }

    DestroyAVLTree(root->left);
    DestroyAVLTree(root->right);

    free(root);
}

node* DeleteNode(node* cur, int val)
{
    if (cur == nullptr) return cur;

    if (cur->data > val)
    {
        cur->left = DeleteNode(cur->left, val);
    }
    else if (cur->data < val)
    {
        cur->right = DeleteNode(cur->right, val);
    }
    else
    {
        if (cur->right == nullptr && cur->left == nullptr)
        {
            free(cur);
            cur = nullptr;
        }
        else if (!(cur->right && cur->left) && (cur->left || cur->right))
        {
            node* tem = nullptr;
            if (cur->left)
                tem = cur->left;
            else
                tem = cur->right;

            cur->data = tem->data;
            cur->left = cur->right = nullptr;
            delete tem;
        }
        else
        {
            node* tem = cur->right;

            while (tem->left != nullptr)
                tem = tem->left;

            cur->data = tem->data;
            cur->right = DeleteNode(cur->right, tem->data);
        }
    }

    if (cur == nullptr) return cur;

    updataHeight(cur);

    int br = GetBalance(cur);
    int bl = GetBalance(cur->left);
    int brr = GetBalance(cur->right);

    //LL
    if (br > 1 && bl >= 0)
    {
        return RightRotate(cur);
    }

    //LR
    if (br > 1 && bl < 0)
    {
        cur->left = LeftRotate(cur->left);
        return RightRotate(cur);
    }

    //RR
    if (br < -1 && brr <= 0)
    {
        return LeftRotate(cur);
    }

    //RL
    if (br < -1 && brr > 0)
    {
        cur->right = RightRotate(cur->right);
        return LeftRotate(cur);
    }

    return cur;
}

node* LeftRotate(node* root)
{
    if (root == nullptr)
        return root;

    node* newroot = root->right;
    node* tem = newroot->left;

    newroot->left = root;
    root->right = tem;

    updataHeight(root);
    updataHeight(newroot);

    return newroot;
}

node* RightRotate(node* root)
{
    if (root == nullptr)
        return root;

    node* newroot = root->left;
    node* tem = newroot->right;

    newroot->right = root;
    root->left = tem;

    updataHeight(root);
    updataHeight(newroot);

    return newroot;
}

node* InsertAVLTree(node* root, int val)
{
    if (root == nullptr)
    {
        return BuyNode(val);
    }

    if (root->data < val)
    {
        root->right = InsertAVLTree(root->right, val);
    }
    else if (root->data > val)
    {
        root->left = InsertAVLTree(root->left, val);
    }

    updataHeight(root);

    int br = GetBalance(root);
    int bl = GetBalance(root->left);
    int brr = GetBalance(root->right);

    //LL
    if (br > 1 && bl > 0)
    {
        return RightRotate(root);
    }

    //LR
    if (br > 1 && bl < 0)
    {
        root->left = LeftRotate(root->left);
        return RightRotate(root);
    }

    //RR
    if (br < -1 && brr < 0)
    {
        return LeftRotate(root);
    }

    //RL
    if(br < -1 && brr > 0)
    {
        root->right = RightRotate(root->right);
        return LeftRotate(root);
    }

    return root;

}
二叉树AVl
版权声明：如无特殊标注，文章均来自网络，本站编辑整理，转载时请以链接形式注明文章出处，请自行分辨。

本文链接：https://www.shbk5.com/dnsj/74177.html

上一篇oled48cx（有用过华硕ROG巨擎 48 OLED电竞显示器的吗，值得入吗）

下一篇oppo u701t 移动版（我的OPPO U701T经常提示有流量超了的现象，这个怎么弄）

相关文章

热门文章

最新发布

标签列表