[Data Structure] Tree(3) - AVL Tree

"AVL 트리"는 자가 균형(Self-Balancing) 이진 검색 트리로, 좌우 서브 트리의 높이 차이가 1을 유지한다. 

만약, 높이 차이가 1 이상이 나게 된다면 스스로 균형을 맞추어 높이 차이 1을 유지한다. 

 

이전 포스팅에서 보았던 이진 검색 트리의 경우에는 최악의 경우 모든 연산의 시간복잡도가 $O(N)$이 되었다. 

이는 다음과 같이 편향트리가 될 수 있기 때문이다. 

 

따라서, AVL트리는 자가 균형을 통해 높이차를 1을 유지함으로써, 모든 연산의 평균 최악 모두 $O(logN)$을 보장한다. 

 

Balance Factor 

이진 트리에서 Balance Factor는 다음과 같이 정의된다. 

즉, 오른쪽 서브트리의 높이에서 왼쪽 서브트리의 높이를 뺀 값이다. 

AVL 트리는 BF값이 [-1, 1]범위 내에 있음을 보장한다. 

 

음수의 값을 가지게 되면 왼쪽 서브트리가 더 높은 것을 뜻하며,

양수의 값을 가지게 되면 오른쪽 서브트리가 더 높은 것을 뜻한다. 

 

Rotation 

AVL트리는 삽입, 삭제, 검색 연산이 이진 검색 트리와 동일하게 수행되지만, 

불균형이 일어나는 경우 Rotation 연산을 통해 균형을 맞춘다. 

 

이때, BF값이 범위를 벗어난 최초의 노드를 "불균형 노드"라 하는데,

Rotation연산은 이 불균형 노드를 기준으로 수행된다. 

 

이때, 불균형 노드(Z)는 총 4개의 경우가 존재하며, 각각 다른 Rotaion을 수행한다. 

• RR Case : Left Rotate
• LL Case : Right Rotate
• RL Case : Right Lotate + Left Rotate
• LR Case : Left Rotate + Right Rotate

 

RR(Right Right) Case - Left Rotation

불균형 노드(Z)를 기준으로 오른쪽 자식 노드의, 오른쪽 자식노드가 존재하는 경우이다. 

(BF(Z) >= 2 이고, Z의 오른쪽 자식을 Y, Y의 오른쪽 자식을 X라 하자)

이러한 경우 Left Rotation을 통해 균형을 맞춘다.

Left Rotation의 수행과정은 다음과 같다. 

• Y노드의 왼쪽 자식노드를 Z노드로 지정한다. 
• Y의 왼쪽 서브트리(T2)를 Z노드의 오른쪽 서브트리로 지정한다. 

 

LL (Left Left) Case - Right Rotation

불균형 노드(Z)를 기준으로 왼쪽 자식 노드의, 왼쪽 자식노드가 존재하는 경우이다.

(BF(Z) <= -2 이고, Z의 왼쪽 자식을 Y, Y의 왼쪽 자식을 X라 하자)

해당 경우에는 Right Rotation을 통해 균형을 맞춘다. 

• Y노드의 오른쪽 자식을 Z노드로 지정한다. 
• Y의 오른쪽 서브트리(T2)를 Z의 왼쪽 서브트리로 지정한다. 

 

 

RL(Right Left) Case

불균형 노드(Z)를 기준으로 오른쪽 자식 노드의, 왼쪽 자식노드가 존재하는 경우이다.

(BF(Z) >= 2 이고, Z의 오른쪽 자식을 Y, Y의 왼쪽 자식을 X라 하자)

우선 Y를 기준으로 Right Rotation 작업을 수행한다. 

• X노드의 오른쪽 자식을 Y노드로 지정한다. 
• X의 오른쪽 서브트리(T3)를 Y의 왼쪽 서브트리로 지정한다.  

한번 Right Rotatation 수행하게 되면, RR Case가 된다 

따라서, Z노드를 기준으로 Left Rotation을 수행하면 된다.

 

LR(Left Right) Case

불균형 노드(Z)를 기준으로 왼쪽 자식 노드의, 오른쪽 자식노드가 존재하는 경우이다.

(BF(Z) >= 2 이고, Z의 왼쪽 자식을 Y, Y의 오른쪽 자식을 X라 하자)

우선, Y노드를 기준으로 Left Roation을 수행한다. 

• X노드의 왼쪽 자식을 X노드로 지정한다. 
• X노드의 왼쪽 서브트리(T2)를 Y의 오른쪽 서브트리로 지정한다. 

이후, LL Case가 되어, Z노드를 기준으로 Right Rotation을 수행하면 된다. 

 

 

구현 

전체적인 구현은 여기에서 살펴볼 수 있다. 

https://github.com/jungseokyoung-cloud/Data-Structure/tree/main/Data-Structure/Tree.playground/Sources

Data-Structure/Data-Structure/Tree.playground/Sources at main · jungseokyoung-cloud/Data-Structure

우선, 앞서 말했다 싶이 기본적인 연산은 BST와 동일하게 수행되기에, 저번 포스팅에서 구현했던 BST를 상속받는다. 

public class AVLTree<T: Comparable>: BinarySearchTree<T> {
	/// tree에 값을 추가합니다.
	public override func insert(_ value: T) {
		super.insert(value)
		
		if let root = self.root {
			self.balance(for: root)
		}
	}
	
	public override func remove(_ value: T) -> T? {
		let value = super.remove(value)

		if let root = self.root {
			self.balance(for: root)
		}
		
		return value
	}
}

 

이후, insert(_:), remove(_:) 메서드를 오버라이드해 balance(for:) 메서드를 호출한다. 

 

balance(for:)

func balance(for node: Node<T>) {
	if let leftChild = node.left {
		balance(for: leftChild)
	} else if let rightChild = node.right{
		balance(for: rightChild)
	}
	
	rotate(for: node)
	updateHeight(for: node)
}

balance(for:)메서드는 다음과 같이 재귀적으로 호출해 리프노드부터 rotate(for:) 작업을 진행하고, updateHeight(for:)메서드를 통해 높이를 갱신합니다. 

 

rotate(for:)

/// 회전을 한 후, 회전을 진행한 서브트리의 루트노드를 리턴합니다.
func rotate(for node: Node<T>) -> Node<T> {
	guard node.balanceFactor > 1 || node.balanceFactor < -1 else { return node }
	if node.balanceFactor == 2, let rightChild = node.right {
		// RL Case
		if let leftChild = rightChild.left {
			let pivot = rightRotate(for: rightChild, pivot: leftChild)
			return leftRotate(for: node, pivot: pivot)
			
		// RR Case
		} else {
			return leftRotate(for: node, pivot: rightChild)
		}
	
	} else if node.balanceFactor == -2, let leftChild = node.left {
		// LR Case
		if let rightChild = leftChild.right {
			let pivot = leftRotate(for: leftChild, pivot: rightChild)
			return rightRotate(for: node, pivot: pivot)
			
		// LL Case
		} else {
			return rightRotate(for: node, pivot: leftChild)
		}
	}
	
	return node
}

rotate(for:) 메서드는 우선, balanceFactor가 [-1, 1] 범위 내에 있는 경우 guard문을 통해 수행하지 않는다. 

이후, RR, RL, LL, LR 케이스 별로 적절한 rotate 함수를 호출한다. 

 

rightRotate(for:pivot:)

@discardableResult
func rightRotate(for node: Node<T>, pivot: Node<T>) -> Node<T> {
	node.left = pivot.right
	node.left?.parent = node
	
	if node.isRightChild {
		node.parent?.right = pivot
	} else {
		node.parent?.left = pivot
	}
	pivot.parent = node.parent
	pivot.right = node
	node.parent = pivot
	
	if node === root { setRoot(to: pivot) }
	
	updateHeight(for: node)
	updateHeight(for: pivot)
	
	return pivot
}

rightRotate(for:pivot:) 메서드는 다음과 같이 수행한다. 

불균형 노드(Z)를 pivot(Y) 기준으로 오른쪽으로 rotate작업을 진행한다. 

 

leftRotate(for:pivot:)

@discardableResult
func leftRotate(for node: Node<T>, pivot: Node<T>) -> Node<T> {
	node.right = pivot.left
	node.right?.parent = node
	
	if node.isRightChild {
		node.parent?.right = pivot
	} else {
		node.parent?.left = pivot
	}
	pivot.parent = node.parent
	pivot.left = node
	node.parent = pivot
	
	if node === root { setRoot(to: pivot) }
	
	updateHeight(for: node)
	updateHeight(for: pivot)
	
	return pivot
}

leftRotation(for:pivot:)메서드는 불균형 노드(Z)를 pivot(Y)기준으로 왼쪽으로 rotate한다.

 

시간복잡도 개선 

다음과 같은 방식은 balance에서 모든 노드를 방문하게 된다. 

func balance(for node: Node<T>) {
	if let leftChild = node.left {
		balance(for: leftChild)
	} else if let rightChild = node.right{
		balance(for: rightChild)
	}
	
	rotate(for: node)
	updateHeight(for: node)
}

따라서 balance의 시간복잡도는 $O(N)$이 소요되어, 최종적으로 삽입 삭제 연산이 $O(N)$이 소요되게 된다. 

 

이를 개선하기 위해서는, 삽입 및 삭제가 일어난 노드에서 부모를 타고 올라가는 경로에만 balance를 적용하면 된다. 

이를 적용하게 되면, $O(logN)$로 개선할 수 있다. 

 

insert(_:)

우선, BST의 코드부터 리팩토링 해보자. 

// BinarySearchTree.swift

/// tree에 값을 추가합니다.
public func insert(_ value: T) {
	performInsert(value)
}

/// Insert 작업을 수행한 후, 삽입된 노드를 리턴합니다.
@discardableResult
func performInsert(_ value: T) -> Node<T>? {
	guard let root else {
		self.root = Node(value: value)
		return root
	}
	
	// 이미 값이 존재하는 경우
	if let node = search(value) {
		node.value = value
		return node
	}
	
	var current = root
	size += 1
	while true {
		if current.value > value {
			if let next = current.left {
				current = next
			} else {
				let node = Node(value: value, parent: current)
				current.left = node
				
				return node
			}
		} else {
			if let next = current.right {
				current = next
			} else {
				let node = Node(value: value, parent: current)
				current.right = node
				
				return node
			}
		}
	}
}

다음과 같이 performInsert메서드는 internal 메서드이며, 삽입된 노드를 리턴한다. 

 

이후, AVL 트리에선 다음과 같이 적용해준다. 

// AVLTree.swift

public override func insert(_ value: T) {
	let insertNode = super.performInsert(value)
	var current = insertNode
	
	while let temp = current {
		current = self.balance(for: temp).parent
	}
}

다음과 같이 삽입된 노드로 부터 루트에 도달할때까지 balance작업을 진행한다. 

/// 균형을 잡힌 서브트리의 루트노드를 리턴합니다.
func balance(for node: Node<T>) -> Node<T> {
	let node = rotate(for: node)
	updateHeight(for: node)
	return node
}

 

remove(_:)

remove 역시 마찬가지로 우선 BST부터 리팩토링한다.

// BinarySearchTree.swift
// MARK: - Remove Method
public func remove(_ value: T) -> T? {
	guard let node = search(value) else { return nil }
	
	defer { performRemove(node: node) }
	
	return node.value
}

/// Remove작업을 수행한 후, 삭제된 위치의 노드를 리턴합니다.
@discardableResult
func performRemove(node: Node<T>) -> Node<T>? {
	defer { size -= 1 }
	
	// 리프 노드인 경우
	if node.isLeaf {
		return removeLeafNode(node)
		
		// 왼쪽 자식만 존재하는 경우
	} else if let leftNode = node.left, node.right == nil {
		return removeOneChildNode(node, child: leftNode)
		
		// 오른쪽 자식만 존재하는 경우
	} else if let rightNode = node.right, node.left == nil {
		return removeOneChildNode(node, child: rightNode)
		
		// 자식이 두개인 노드인 경우
	} else {
		guard let rightNode = node.right else { return nil }
		let successor = successor(from: rightNode)
		
		return removeTwoChildNode(node, successor: successor)
	}
}

 

이후 AVLTree에선 다음과 같이 구현해주면 된다. 

public override func remove(_ value: T) -> T? {
	guard let removeNode = search(value) else { return nil }
	
	defer {
		let node = super.performRemove(node: removeNode)
		var current = node
		
		while let temp = current {
			current = self.balance(for: temp).parent
		}
	}
	
	return removeNode.value
}

다음과 같이 리턴하게 되면, 모든 노드가 아닌 불균형이 일어날 수 있는 경로의 노드만 검사해 $O(logN)$이 소요된다.

 

 

References

위키백과 

• AVL Tree

https://github.com/kodecocodes/swift-algorithm-club/blob/master/AVL%20Tree/AVLTree.swift#L170