daily pastebin goal
39%
SHARE
TWEET

Untitled

a guest Dec 10th, 2018 52 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # AVL tree
  2. - self balancing binary search tree
  3. - binary search tree의 성능을 O(log n)으로 보장한다
  4.  
  5. ## perfect balance
  6. - 좌우 대칭
  7. - 노드가 모두 채워진 상태
  8.  
  9.  
  10. ## balanced
  11. - 마지막 레벨을 제외하고 노드가 모두 채워진 상태
  12.  
  13.  
  14. ## balance factor
  15. - leftChild’s height - rightChild’s height
  16. - 정상범위 : -1 <= factor <= 1
  17.  
  18.  
  19. ## rotation
  20. - left : rightChild에 완전 편중되어 있는 경우 사용
  21. ```swift
  22. public func leftRotate(_ node: AVLNode<Element>) -> AVLNode<Element> {
  23.     let pivot = node.rightChild!
  24.     node.rightChild = pivot.leftChild
  25.     pivot.leftChild = node
  26.     node.height = max(node.leftHeight, node.rightHeight) + 1
  27.     pivot.height = max(pivot.leftHeight, pivot.rightHeight) + 1
  28.     return pivot
  29.   }
  30.  
  31. ```
  32.  
  33. - right : leftChild 에 완전 편중되어 있는 경우 사용
  34. ```swift
  35. public func rightRotate(_ node: AVLNode<Element>) -> AVLNode<Element> {
  36.     let pivot = node.leftChild!
  37.     node.leftChild = pivot.rightChild
  38.     pivot.rightChild = node
  39.     node.height = max(node.leftHeight, node.rightHeight) + 1
  40.     pivot.height = max(pivot.leftHeight, pivot.rightHeight) + 1
  41.     return pivot
  42.   }
  43. ```
  44.  
  45.  
  46. - right- > left : right rotation해서 rightChild 에 완전 편중되게 만든 다음에 left rotation 하기
  47. ```swift
  48. private func rightLeftRotate(_ node: AVLNode<Element>) -> AVLNode<Element> {
  49.     guard let rightChild = node.rightChild else {
  50.       return node
  51.     }
  52.    
  53.     node.rightChild = rightRotate(rightChild)
  54.     return leftRotate(node)
  55.   }
  56. ```
  57.  
  58. - left- > right
  59. ```swift
  60. private func leftRightRotate(_ node: AVLNode<Element>) -> AVLNode<Element> {
  61.     guard let leftChild = node.leftChild else {
  62.       return node
  63.     }
  64.     node.leftChild = leftRotate(leftChild)
  65.     return rightRotate(node)
  66.   }
  67. ```
  68.  
  69.  
  70.  
  71. ## balance factor를 사용해서 밸런싱 하기
  72. ```swift
  73. private func balanced(_ node: AVLNode<Element>) -> AVLNode<Element> {
  74.     switch node.balanceFactor {
  75.     case 2:
  76.       if let leftChild = node.leftChild, leftChild.balanceFactor == -1 {
  77.         return leftRightRotate(node)
  78.       } else {
  79.         return rightRotate(node)
  80.       }
  81.     case -2:
  82.       if let rightChild = node.rightChild, rightChild.balanceFactor == 1 {
  83.         return rightLeftRotate(node)
  84.       } else {
  85.         return leftRotate(node)
  86.       }
  87.      
  88.     default:
  89.       return node
  90.     }
  91.   }
  92. ```
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top