Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # AVL tree
- - self balancing binary search tree
- - binary search tree의 성능을 O(log n)으로 보장한다
- ## perfect balance
- - 좌우 대칭
- - 노드가 모두 채워진 상태
- ## balanced
- - 마지막 레벨을 제외하고 노드가 모두 채워진 상태
- ## balance factor
- - leftChild’s height - rightChild’s height
- - 정상범위 : -1 <= factor <= 1
- ## rotation
- - left : rightChild에 완전 편중되어 있는 경우 사용
- ```swift
- public func leftRotate(_ node: AVLNode<Element>) -> AVLNode<Element> {
- let pivot = node.rightChild!
- node.rightChild = pivot.leftChild
- pivot.leftChild = node
- node.height = max(node.leftHeight, node.rightHeight) + 1
- pivot.height = max(pivot.leftHeight, pivot.rightHeight) + 1
- return pivot
- }
- ```
- - right : leftChild 에 완전 편중되어 있는 경우 사용
- ```swift
- public func rightRotate(_ node: AVLNode<Element>) -> AVLNode<Element> {
- let pivot = node.leftChild!
- node.leftChild = pivot.rightChild
- pivot.rightChild = node
- node.height = max(node.leftHeight, node.rightHeight) + 1
- pivot.height = max(pivot.leftHeight, pivot.rightHeight) + 1
- return pivot
- }
- ```
- - right- > left : right rotation해서 rightChild 에 완전 편중되게 만든 다음에 left rotation 하기
- ```swift
- private func rightLeftRotate(_ node: AVLNode<Element>) -> AVLNode<Element> {
- guard let rightChild = node.rightChild else {
- return node
- }
- node.rightChild = rightRotate(rightChild)
- return leftRotate(node)
- }
- ```
- - left- > right
- ```swift
- private func leftRightRotate(_ node: AVLNode<Element>) -> AVLNode<Element> {
- guard let leftChild = node.leftChild else {
- return node
- }
- node.leftChild = leftRotate(leftChild)
- return rightRotate(node)
- }
- ```
- ## balance factor를 사용해서 밸런싱 하기
- ```swift
- private func balanced(_ node: AVLNode<Element>) -> AVLNode<Element> {
- switch node.balanceFactor {
- case 2:
- if let leftChild = node.leftChild, leftChild.balanceFactor == -1 {
- return leftRightRotate(node)
- } else {
- return rightRotate(node)
- }
- case -2:
- if let rightChild = node.rightChild, rightChild.balanceFactor == 1 {
- return rightLeftRotate(node)
- } else {
- return leftRotate(node)
- }
- default:
- return node
- }
- }
- ```
Add Comment
Please, Sign In to add comment