AVL树（平衡二叉树）图解-创新互联

• 左左型
• 右右型
• 左右型
• 右左型
• 测试及完整代码

本节我们不会主要讲解AVL树的原理，只讨论AVL树的四种旋转的情形，有关AVL树的基本知识请看其他博客。

对于左左型的AVL树，我们只需对它进行一次左旋即可：

void AVLTree::SingleRotateWithLeft(TreeNode*& root)
{//左左型
	TreeNode* K2 = root;

	TreeNode* K1 = K2->left;
	K2->left = K1->right;
	K1->right = K2;
	//K1经过旋转后成为了新的根节点，K2是其右孩子

	K2->height = max(Height(K2->left), Height(K2->right)) + 1;
	K1->height = max(Height(K1->left), K2->height) + 1;

	root = K1;	//根节点重新确认
}

对于右右型的AVL树，我们只需对它进行一次左旋即可：

void AVLTree::SingleRotateWithRight(TreeNode*& root)
{//右右型
	TreeNode* K1 = root;

	TreeNode* K2 = K1->right;
	K1->right = K2->left;
	K2->left = K1;
	//K1经过旋转后成为了新的根节点，K2是其左孩子

	K1->height = max(Height(K1->left), Height(K1->right)) + 1;
	K2->height = max(K1->height, Height(K2->right)) + 1;

	root = K2;
}

对于左右型的AVL树，我们只需对它进行一次右旋，然后进行一次左旋即可：

void AVLTree::DoubleRotateWithLeft(TreeNode*& root)
{//左右型
	TreeNode* K3 = root;
	//1. 先右旋
	SingleRotateWithRight(K3->left);
	//2. 后左旋
	SingleRotateWithLeft(K3);

	root = K3;
}

对于右左型的AVL树，我们只需对它进行一次左旋，然后进行一次右旋即可：

void AVLTree::DoubleRotateWithRight(TreeNode*& root)
{//右左型
	TreeNode* K3 = root;
	//1. 先左旋
	SingleRotateWithLeft(K3->right);
	//2. 再右旋
	SingleRotateWithRight(K3);

	root = K3;
}

#includeusing namespace std;

using Type = int;

struct TreeNode
{Type data;
	TreeNode* left;
	TreeNode* right;
	int height = 0;
	TreeNode(const Type& data, TreeNode* left = nullptr, TreeNode* right = nullptr, const int& height = 0)
		:data(data), left(left), right(right),height(height) {}
};

class AVLTree
{public:
	AVLTree();
	~AVLTree();
	//计算AVL树的节点高度
	static int Height(TreeNode* node);
	void insert(const Type& data);
private:
	void SingleRotateWithLeft(TreeNode*& root);
	void SingleRotateWithRight(TreeNode*& root);
	void DoubleRotateWithLeft(TreeNode*& root);
	void DoubleRotateWithRight(TreeNode*& root);
	void _insert(const Type& data, TreeNode*& root);
private:
	TreeNode* root;
};

int main()
{AVLTree t1, t2, t3, t4;

	//右右型
	t1.insert(1);
	t1.insert(2);
	t1.insert(3);

	//左左型
	t2.insert(3);
	t2.insert(2);
	t2.insert(1);

	//左右型
	t3.insert(3);
	t3.insert(1);
	t3.insert(2);

	//右左型
	t4.insert(1);
	t4.insert(3);
	t4.insert(2);

	AVLTree t;
	vectorvec{4,2,6,1,3,5,7,16,15,14,13,12,11,10,8,9 };
	for (int i = 0; i< vec.size(); i++)
	{t.insert(vec[i]);
	}
	return 0;
}

AVLTree::AVLTree()
{root = nullptr;
}

AVLTree::~AVLTree()
{//销毁整棵树
}

int AVLTree::Height(TreeNode* node)
{if (node == nullptr)
	{return -1;
	}
	else
	{return node->height;
	}
}

void AVLTree::insert(const Type& data)
{_insert(data, root);
}

void AVLTree::SingleRotateWithLeft(TreeNode*& root)
{//左左型
	TreeNode* K2 = root;

	TreeNode* K1 = K2->left;
	K2->left = K1->right;
	K1->right = K2;
	//K1经过旋转后成为了新的根节点，K2是其右孩子

	K2->height = max(Height(K2->left), Height(K2->right)) + 1;
	K1->height = max(Height(K1->left), K2->height) + 1;

	root = K1;
}

void AVLTree::SingleRotateWithRight(TreeNode*& root)
{//右右型
	TreeNode* K1 = root;

	TreeNode* K2 = K1->right;
	K1->right = K2->left;
	K2->left = K1;
	//K1经过旋转后成为了新的根节点，K2是其左孩子

	K1->height = max(Height(K1->left), Height(K1->right)) + 1;
	K2->height = max(K1->height, Height(K2->right)) + 1;

	root = K2;
}

void AVLTree::DoubleRotateWithLeft(TreeNode*& root)
{//左右型
	TreeNode* K3 = root;
	//1. 先右旋
	SingleRotateWithRight(K3->left);
	//2. 后左旋
	SingleRotateWithLeft(K3);

	root = K3;
}

void AVLTree::DoubleRotateWithRight(TreeNode*& root)
{//右左型
	TreeNode* K3 = root;
	//1. 先左旋
	SingleRotateWithLeft(K3->right);
	//2. 再右旋
	SingleRotateWithRight(K3);

	root = K3;
}

void AVLTree::_insert(const Type& data, TreeNode*& root)
{if (root == nullptr)
	{root = new TreeNode{data };
		return;
	}
	if (data< root->data)
	{//左子树插入
		_insert(data, root->left);
		if (Height(root->left) - Height(root->right) == 2)
		{	if (data< root->left->data)
			{		SingleRotateWithLeft(root);	//单旋转：左左型
			}
			else
			{		DoubleRotateWithLeft(root);	//双旋转：左右型
			}
		}
	}
	else if (data >root->data)
	{//右子树插入
		_insert(data, root->right);
		if (Height(root->right) - Height(root->left) == 2)
		{	if (data >root->right->data)
			{		SingleRotateWithRight(root);	//单旋转：右右型
			}
			else
			{		DoubleRotateWithRight(root);	//双旋转：右左型
			}
		}
	}
	//否则树已经在节点中了，我们什么也不做

	//update树节点的高度
	root->height = max(Height(root->left), Height(root->right)) + 1;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧