[Algorithm - Concept] AVL Tree (named after inventors Adelson-Velsky and Landis)

[Algorithm - Concept] AVL Tree (named after inventors Adelson-Velsky and Landis)

---

https://en.wikipedia.org/wiki/AVL_tree

 

AVL 트리(AVL tree)는 가장 초기에 나온 균형 잡힌(balanced) 이진 탐색 트리이다. 1962년 G.M. Adelson-Velskii와 E.M. Landis 가 그들의 논문 "An algorithm for the organization of information" 을 통해 발표했고 그들의 이름을 따서 지어졌다. AVL 트리는 각각의 노드(node, 분기점)마다 왼쪽과 오른쪽 부분 트리(sub-tree)의 높이 차이에 대한 정보를 가지며 부분 트리의 높이 차이가 1보다 크지 않은 성질을 가진다. 균형 잡힌 AVL 트리는 n개의 원소가 있을 때 O(log n) 의 시간복잡도로 검색, 삽입, 삭제를 할 수 있다. 그러나 삽입과 삭제를 할 때에는 원하는 노드를 찾기 위해 2개의 경로가 필요하기 때문에 레드-블랙 트리 만큼 효율이 좋지 않아 자주 쓰이지는 않는다.

 

In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations. The AVL tree is named after its two Soviet inventors, Georgy Adelson-Velsky and Evgenii Landis, who published it in their 1962 paper "An algorithm for the organization of information".

---

💊 알고리즘 복잡도 (Algorithm Complcomplexity)

⏰ 시간 복잡도 (Time Complcomplexity)	O(log N)
📦 공간 복잡도 (Space Complcomplexity)	O(N)

---

📄 [Algorithm] AVL Tree Algorithm C++ Source Code

#include <iostream>
using namespace std;

/* Typedef */
typedef struct node * NodePtr;

/* Struct */
typedef struct node
{
	int mData;
	NodePtr mLeft = NULL;
	NodePtr mRight = NULL;
} Node;

/* Function */
int GetHeight(NodePtr bst)
{
	int leftH; /* Left Hight */
	int rightH; /* Right Hight */

				/* 연결 된 노드가 없는 경우 */
	if (bst == NULL) return 0;

	leftH = GetHeight(bst->mLeft); /* 왼쪽 서브트리 높이 계산 */
	rightH = GetHeight(bst->mRight); /* 오른쪽 서브트리 높이 계산 */

									 /* 큰 값의 높이를 반환 */
	return leftH > rightH ? leftH + 1 : rightH + 1;
}
int GetHeightDiff(NodePtr bst)
{
	int lsh; /* left sub tree hight */
	int rsh; /* right sub tree hight */

			 /* 연결 된 노드가 없는 경우 */
	if (bst == NULL) return 0;

	lsh = GetHeight(bst->mLeft); /* 왼쪽 서브트리의 높이 */
	rsh = GetHeight(bst->mRight); /* 오른쪽 서브트리의 높이 */

	return lsh - rsh; /* 균형 인수 계산 결과 반환 (왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이) */
}
NodePtr RotateLL(NodePtr bst) /* Left-Left Rotate */
{
	/* Node */
	NodePtr pNode = bst; /* Parent Node */
	NodePtr cNode = pNode->mLeft; /* Child Node */

								  /* Left-Left Rotate */
	pNode->mLeft = cNode->mRight;
	cNode->mRight = pNode;

	/* LL Rotate로 인하여 변경 된 루트 노드의 주소 값 반환 */
	return cNode;
}
NodePtr RotateRR(NodePtr bst) /* Right-Right Rotate */
{
	/* Node */
	NodePtr pNode = bst; /* Parent Node */
	NodePtr cNode = pNode->mRight; /* Child Node */

								   /* Right-Right Rotate */
	pNode->mRight = cNode->mLeft;
	cNode->mLeft = pNode;

	/* RR Rotate로 인하여 변경 된 루트 노드의 주소 값 반환 */
	return cNode;
}
NodePtr RotateLR(NodePtr bst) /* Left-Right Rotate */
{
	/* Node */
	NodePtr pNode = bst; /* Parent Node */
	NodePtr cNode = pNode->mLeft; /* Child Node */

								  /* Left-Right Rotate */
	pNode->mLeft = RotateRR(cNode); /* Sub Right-Right Rotate */
	return RotateLL(pNode); /* Left-Left Rotate */
}
NodePtr RotateRL(NodePtr bst) /* Right-Left Rotate */
{
	/* Node */
	NodePtr pNode = bst; /* Parent Node */
	NodePtr cNode = pNode->mRight; /* Child Node */

								   /* Right-Left Rotate */
	pNode->mRight = RotateLL(cNode); /* Sub Left-Left Rotate */
	return RotateRR(pNode); /* Right-Right Rotate */
}
NodePtr Rebalance(NodePtr * pRoot)
{
	/* Integer */
	int hDiff = GetHeightDiff(*pRoot); /* 균형 인수 계산 */

									   /* 균형 인수가 +2 이상이면 LL 상태 또는 LR 상태이다. */
	if (hDiff > 1)
	{
		*pRoot = GetHeightDiff((*pRoot)->mLeft) > 0 ? RotateLL(*pRoot) : RotateLR(*pRoot);
	}

	/* 균형 인수가 -2 이하이면 RR 상태 또는 RL 상태이다. */
	if (hDiff < -1)
	{
		*pRoot = GetHeightDiff((*pRoot)->mRight) < 0 ? RotateRR(*pRoot) : RotateRL(*pRoot);
	}

	return *pRoot;
}
void MakeLeftSubTree(NodePtr mRoot, NodePtr mSub)
{
	if (mRoot->mLeft != NULL) { delete (mRoot->mLeft); }
	mRoot->mLeft = mSub;
}
void MakeRightSubTree(NodePtr mRoot, NodePtr mSub)
{
	if (mRoot->mRight != NULL) { delete (mRoot->mRight); }
	mRoot->mRight = mSub;
}
NodePtr BSTInsert(NodePtr * mRoot, int data)
{
	if (*mRoot == NULL) { (*mRoot) = new Node(); (*mRoot)->mData = data; } /* Root Node인 경우 */
	else if (data < (*mRoot)->mData) { BSTInsert(&((*mRoot)->mLeft), data); *mRoot = Rebalance(mRoot); }
	else if (data > (*mRoot)->mData) { BSTInsert(&((*mRoot)->mRight), data); *mRoot = Rebalance(mRoot); }
	else { return NULL; } /* 중복 Key 값이 저장되는 경우 */

	return (*mRoot);
}
NodePtr BSTSearch(NodePtr mFind, int target)
{
	/* Node */
	NodePtr cNode = mFind; /* Current Node */

	while (cNode != NULL)
	{
		if (target == cNode->mData) { return cNode; } /* 찾고자 하는 값은 찾은 경우 Node 반환 */
		else if (target < cNode->mData) { cNode = cNode->mLeft; } /* 찾고자 하는 값보다 큰 경우 현재 노드의 왼쪽 주소 반환 */
		else { cNode = cNode->mRight; } /* 찾고자 하는 값보다 작은 경우 현재 노드의 오른쪽 주소 반환 */
	}

	return NULL; /* 탐색대상이 저장되어 있지 않은 경우 */
}
NodePtr RemoveLeftSubTree(NodePtr mNode)
{
	/* Node */
	NodePtr delNode = NULL;

	if (mNode != NULL)
	{
		delNode = mNode->mLeft;
		mNode->mLeft = NULL;
	} return delNode;
}
NodePtr RemoveRightSubTree(NodePtr mNode)
{
	/* Node */
	NodePtr delNode = NULL;

	if (mNode != NULL)
	{
		delNode = mNode->mRight;
		mNode->mRight = NULL;
	} return delNode;
}
NodePtr BSTDelete(NodePtr * pRoot, int target)
{
	/* Node */
	NodePtr pVRoot = new Node; /* 가상 루트 노드 */
	NodePtr pNode = pVRoot; /* Parent Node */
	NodePtr cNode = *pRoot; /* Current Node */
	NodePtr dNode = NULL; /* Delete Node */

						  /* Root Node를 가상 루트 로드가 가리키는 노드의 오른쪽 자식 노드가 되게 한다. */
	pVRoot->mRight = *pRoot;

	/* 삭제 대상인 노드를 탐색 */
	while (cNode != NULL && cNode->mData != target)
	{
		pNode = cNode;

		if (target < cNode->mData) { cNode = cNode->mLeft; }
		else { cNode = cNode->mRight; }
	}

	/* 삭제할 대상이 존재하지 않는 경우 */
	if (cNode == NULL) { return NULL; }

	dNode = cNode; /* 삭제 대상을 dNode가 가리키게 한다. */

				   /* 첫번째 경우 : 삭제 대상이 단말 노드인 경우 */
	if (dNode->mLeft == NULL && dNode->mRight == NULL)
	{
		pNode->mLeft == dNode ? RemoveLeftSubTree(pNode) : RemoveRightSubTree(pNode);
	}
	/* 두번째 경우 : 삭제 대상이 하나의 자식 노드를 갖는 경우 */
	else if (dNode->mLeft == NULL || dNode->mRight == NULL)
	{
		/* Node */
		NodePtr dcNode = (dNode->mLeft != NULL ? dNode->mLeft : dNode->mRight); /* 삭제 대상의 자식노드를 가리킨다. */

		pNode->mreturn 0;
}

---

🚀 REFERENCE

AVL tree - Wikipedia

ChangYeop-Yang/Study-DataStructure