# 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
    }
  }
```