AVL 트리

AVL 트리의 정의

ㆍ 균형 잡힌 높이의 이진 검색 트리이다.

ㆍ 두 개의 자식 노드들 간에 깊이 차이가 1 이하인 트리이다.

---

AVL 트리의 장점

ㆍ 트리의 검색 연산이 항상 O(log n)으로 균형 잡혀 있다.

ㆍ 트리의 삭제 연산 또한 O(log n)으로 균형 잡혀 있다.

---

AVL 트리의 단점

ㆍ 삽입 연산이 이루어질 때 트리의 재구성 시간이 소요된다.

ㆍ 이진 검색 트리보다 구현의 난이도가 높다.

---

구현 방법

relink() 메서드

protected void relink(Node<K, V> parent, Node<K, V> child, boolean makeLeft) {
	if (child != null)
		child.parent = parent;
	if (makeLeft)
		parent.left = child;
	else
		parent.right = child;
}

ㆍ 자식 노드를 부모 노드의 자식으로 연결시킨다.

ㆍ makeLeft가 참이라면 부모의 왼쪽 자식으로, 거짓이라면 오른쪽 자식으로 만든다.

 

rotate() 메서드

protected void rotate(Node<K, V> x) {
	Node<K, V> y = x.parent;
	Node<K, V> z = y.parent;
	if (z == null) {
		root = x;
		x.parent = null;
	} else
		relink(z, x, y == z.left);

	if (x == y.left) {
		relink(y, x.right, true);
		relink(x, y, false);
	} else {
		relink(y, x.left, false);
		relink(x, y, true);
	}
}

ㆍ 재구성하고자 하는 트리의 모양이 LL, RR일 경우의 호출되는 메서드이다.

ㆍ 트리의 모양을 LL과 RR의 경우일 때로 구분하여 relink() 메서드를 호출하여 트리를 재구성한다.

 

restructure() 메서드

protected Node<K, V> restructure(Node<K, V> x) {
	Node<K, V> y = x.parent;
	Node<K, V> z = y.parent;
	if ((x == y.left) == (y == z.left)) {
		rotate(y);
		return y;
	} else {
		rotate(x);
		rotate(x);
		return x;
	}
}

ㆍ 트리의 모양이 LL 혹은 RR이면 rotate() 메서드를 호출하여 재구성한다.
ㆍ 트리의 모양이 LR 혹은 RL인 경우에는 rotate() 메서드로 LL 또는 RR의 형태로 바꾼다.
ㆍ LL 또는 RR 형태의 트리를 다시 한번 rotate() 메서드를 호출하여 트리를 재구성한다.

 

getHeight() 메서드

private int getHeight(Node<K, V> x) {
	return (x == null) ? 0 : x.getAux();
}

ㆍ 특정 노드의 높이를 반환하는 메서드이다.

 

setHeight() 메서드

private void setHeight(Node<K, V> x, int height) {
	x.setAux(height);
}

ㆍ 특정 노드의 높이를 설정하는 메서드이다.

 

recomputeHeight() 메서드

private void recomputeHeight(Node<K, V> x) {
	setHeight(x, 1 + Math.max(getHeight(x.left), getHeight(x.right)));
}

ㆍ 트리의 재구성이 이루어질 때 노드의 높이를 재계산하는 메서드이다.

 

isBalanced() 메서드

private boolean isBalanced(Node<K, V> x) {
	return Math.abs(getHeight(x.left) - getHeight(x.right)) <= 1;
}

ㆍ 특정 노드를 기준으로 자식 노드들이 균형을 이루는지를 확인하는 메서드이다.

 

tallerChild() 메서드

private Node<K, V> tallerChild(Node<K, V> x) {
	if (getHeight(x.left) > getHeight(x.right))
		return x.left;
	if (getHeight(x.left) < getHeight(x.right))
		return x.right;
	if (x == root)
		return x.left;
	if (x == x.parent.left)
		return x.left;
	else
		return x.right;
}

ㆍ 특정 노드의 자식 노드 중 깊이가 깊은 자식 노드를 반환하는 메서드이다.

 

rebalance() 메서드

private void rebalance(Node<K, V> x) {
	do {
		if (!isBalanced(x)) {
			x = restructure(tallerChild(tallerChild(x)));
			recomputeHeight(x.left);
			recomputeHeight(x.right);
			for (Node<K, V> p = x; p != null; p = p.parent)
				recomputeHeight(p);
		}
		x = x.parent;
	} while (x != null);
}

ㆍ rebalanceInsert() 메서드와 rebalanceDelete() 메서드에서 재구성을 위하여 호출되는 메서드이다.
ㆍ 트리를 재구성하기 위해 호출되는 메서드이다.

---

참고 문헌 및 자료

ㆍ R.Sedgewick and K. Wayne, Algorithms (4th Ed.), Addison-Wesley.

ㆍ E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, Silicon Press, 2nd Edition.

---

GitHub - qlsdud0604/algorithm-study: 자료구조 및 알고리즘 공부 기록 공간