Detaillierte Code-Erklärung zum Einfügen des AVL-Baums

Der AVL-Baum wird als binärer Suchbaum mit Höhenausgleich bezeichnet. Versuchen Sie, die Höhe des Binärbaums so weit wie möglich zu reduzieren, um das Gleichgewicht des Binärbaums aufrechtzuerhalten und die durchschnittliche Suchlänge des Baums zu verringern.

Eigenschaften des AVL-Baums: 1. Der Unterschied (absoluter Wert) zwischen den Höhen des linken Teilbaums und des rechten Teilbaums überschreitet nicht 1

2. Jeder Teilbaum im Baum ist AVL-Baum,

3. Jeder Knoten hat einen Gleichgewichtsfaktor mit einem Wert von (-1,0,1). Das Gleichgewicht des Baums wird anhand des Gleichgewichtsfaktors beurteilt.

Die folgenden Situationen müssen beim Einfügen in den AVL-Baum berücksichtigt werden: (Der Pfeil zeigt die Richtung und den einzufügenden Knoten an)

Die erste Situation: Der eingefügte Knoten befindet sich rechts von 20, aber dies führt dazu, dass der Ausgleichsfaktor von 10 größer als 1 ist, daher ist eine Drehung erforderlich, um den Ausgleichsfaktor zu ändern

Der zweite Fall: Einfügen auf left führt dazu, dass der Balance-Faktor auch nicht die Bedingungen erfüllt, die erforderlich sind. Rotation

Der dritte Fall: Der eingefügte Knoten stellt möglicherweise keine einzelne Rotation dar, also a Zur Lösung ist eine doppelte Drehung erforderlich

Vierter Fall: Doppelte Drehung entgegengesetzt zum dritten Fall

In Auf diese Weise kann durch Rotation beim Einfügen ein Gleichgewicht im Binärbaum erreicht werden.

Der Implementierungscode lautet wie folgt:

//main函数

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<assert.h>
using namespace std;
#include"AVLTree.h"

int main()
{
	testAVLTree();
	system("pause");
	return 0;
}

//AVLTree  ---->  被称为高度平衡的二叉搜索树
//使用三叉链来实现此二叉平衡搜索树
//性质：左右高度差不超过1 && 该树的左右子树都为二叉平衡树


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

	K _key;
	V _value;

	int _bf; // 平衡因子

	//构造函数
	AVLTreeNode(const K& key,const V& value) :_left(NULL), _right(NULL), _parent(NULL)
		, _key(key), _value(value), _bf(0)
	{}
};

template<class K,class V>
class AVLTree
{
	typedef AVLTreeNode<K,V> Node;
public:
	AVLTree() :_root(NULL)
	{}
	//使用非递归的插入
	bool Insert(const K& key, const V& value)
	{
		//如果根节点不存在说明插入的节点是第一个节点，直接new 一个即可
		if (_root == NULL){
			_root = new Node(key, value);
			return true;
		}
		Node* cur = _root;
		Node* parent = NULL;
		while (cur)
		{
			if (cur->_key < key){
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key>key){
				parent = cur;
				cur = cur->_left;
			}
			else{
				return false;
			}
		}
			//走到这里，说明这个节点不存在，先new
			cur = new Node(key, value);

			//比较插入节点的值与父节点的值，再考虑链上左还是右
			if (parent->_key < key){
				parent->_right = cur;
				cur->_parent = parent;
			}
			else if (parent->_key>key){
				parent->_left = cur;
				cur->_parent = parent;
			}
			else{
				while (parent)
				{
					//判断cur是插在了parent的左边还是右边，再判断平衡因子是++还是--
					if (cur == parent->_left){
						parent->_bf--;
					}
					else{
						parent->_bf++;
					}
					//++或--之后，判断平衡因子是否等于2或等于-2
					if (parent->_bf == 0)    //等于0说明没有变，则跳出循环
					{
						break;
					}
					else if (parent->_bf == 1 || parent->_bf == -1)
					{
						cur = parent;
						parent = cur->_parent;
					}
					else if (parent->_bf == 2 || parent->_bf == -2)//如果等于2或者等于-2则不再插入，先调节为二叉平衡树再插入
					{
						//根据平衡因子来判断需要调整的树是哪种类型，再选择单旋还是双旋
						//如果父节点的平衡因子等于2，说明右子树比左子树高，再判断右子树的子树是在它的左边还是右边
						if (parent->_bf == 2)
						{
							if (cur->_bf == 1){
								RotateL(parent);
							}
							else{
								RotateRL(parent);
							}
						}
						else
						{
							if (cur->_bf == -1)
								RotateR(parent);
							else
								RotateLR(parent);
						}
					}
				}
			}
			return true;
		}
		//cur = parent;
	//右单旋
	void RotateR(Node* parent)
	{
		//需要记录parent上面是否还有父亲节点
		Node* ppNode = parent->_parent;

		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		//如果subLR存在  就将它的父亲置为parent
		if (subLR)
			subLR->_parent = parent;

		subL->_right = parent;
		parent->_parent = subL;

		//如果parent等于根节点，说明已经到第一个节点，不需要调整，直接将subL作为根即可
		if (parent == _root)
		{
			_root = subL;
			subL->_parent = NULL;
		}
		else   //如果还没有到根节点还需要判断parent是左还是右
		{
			if (ppNode->_left == parent)
				ppNode->_left = subL;
			else{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
	}
	//左单旋
	void RotateL(Node* parent)
	{
		Node* ppNode = parent->_parent;
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		//判断subRL是否存在
		if (subRL){
			subRL->_parent = parent;			
		}
		subR->_left = parent;
		parent->_parent = subRL;
		if (_root == parent)
		{
			_root = subR;
			subR->_parent = NULL;
		}
		else
		{
			if (ppNode->_left == parent)
				ppNode->_left = subR;
			else
				ppNode->_right = subR;
			subR->_parent = ppNode;
		}
	}
	//左右单旋
	void RotateLR(Node* parent)
	{
		RotateL(parent->_right);
		RotateR(parent);
	}
	//右左单旋
	void RotateRL(Node* parent)
	{
		RotateR(parent->_left);
		RotateL(parent);
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}	
	void _InOrder(Node* root)
	{
		if (root == NULL)
			return;
		_InOrder(root->_left);
		cout << root->_key << " ";
		_InOrder(root->_right);
	}
	bool IsBalance()
	{
		return _IsBalance(_root);
	}
	bool _IsBalance(Node* root)
	{
		if (root == NULL)
			return;
		int leftheight = _Height(root->_left);
		int rightheight = _Height(root->_right);
		return abs(rightheight - leftheight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);
	}
	size_t _Height(Node* root)
	{
		if (root == NULL)
			return 0;
		size_t left = _Height(root->_left);
		size_t right = _Height(root->_right);
		return left > right ? left + 1 : right + 1;
	}
private:
	Node* _root;
};

void testAVLTree()
{
	AVLTree<int, int> t;
	int a[] = { 16,3,7,11,9,26,18,14,15};
	for (int i = 0; i < (sizeof(a) / sizeof(a[0])); i++)
	{
		cout<<t.Insert(a[i], 0)<<endl;
	}
	t.InOrder();
}

Das obige ist der detaillierte Inhalt vonDetaillierte Code-Erklärung zum Einfügen des AVL-Baums. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!