[CS] Data Structure Part.5 Binary Search Tree

Hwichan Ji·2020년 11월 9일
0

CS-자료구조

목록 보기
5/7
post-thumbnail

Binary Search Tree

Binary Search Tree란?

이진 탐색 트리는 트리를 구성하는 모든 노드들에 대하여 각 노드의 왼쪽 서브 트리에는 그 노드의 키 값보다 작은 키 값을 가진 노드들만 존재하고 오른쪽 서브 트리에는 그 노드의 키 값보다 큰 키 값을 가진 노드들만 존재하도록 트리를 구성하여 트리에서 이진 탐색이 가능하도록 만든 자료구조입니다.

이진 탐색 트리에서 노드의 키 값은 유일해야하며 모든 서브 트리들도 이진 탐색 트리여야 합니다.

이진 탐색 트리의 구성 조건으로 인해 이진 탐색 트리는 한쪽 방향으로 치우쳐진 편향 트리(Skewed Tree)가 될 수 있습니다.

Operation

탐색

이진 탐색 트리의 탐색 연산은 이진 탐색입니다. 루트 노드부터 시작하여 찾는 값이 현재 노드의 키 값보다 작다면 현재 노드의 왼쪽 서브 트리에 대하여 이진 탐색을 수행하고 크다면 현재 노드의 오른쪽 서브 트리에 대하여 이진 탐색을 수행합니다. 동일하다면 해당 노드를 반환합니다.

이진 탐색 트리의 탐색 연산은 루트 노드 부터 시작하여 Leaf node 까지 도달할 수 있으므로 O(h) 의 시간복잡도를 갖습니다. 따라서 편향 트리일 경우 탐색 연산의 성능이 저하됩니다.

이진 탐색 트리를 중위 순회하면 키 값이 정렬된 순서대로 노드를 방문하게 됩니다.

삽입

이진 탐색 트리의 삽입 연산은 탐색 연산과 같은 과정으로 적절한 삽입 위치를 찾고 그 위치에 새로운 노드를 삽입합니다. 탐색 연산과 마찬가지로 O(h) 의 시간복잡도를 갖습니다.

삭제

이진 탐색 트리의 삭제 연산은 탐색 연산과 같은 과정으로 대상 노드의 위치를 찾고 그 노드를 제거합니다. 제거하는 노드의 자식 노드 수에 따라 추가적인 작업이 필요할 수 있습니다.

  • 자식 노드가 없을 경우에는 대상 노드만 제거합니다.
  • 자식 노드가 하나인 경우에는 대상 노드의 자식 노드와 부모 노드를 연결해야 합니다.
  • 자식 노드가 둘인 경우에는 대상 노드의 오른쪽 서브 트리에서 가장 작은 키 값을 갖는 노드를 찾고 그 노드를 대상 노드에 복사한 뒤 복사하기 전 위치에 있던 노드를 제거해야 합니다.

삭제 연산도 탐색 연산과 마찬가지로 O(h) 의 시간복잡도를 갖습니다.

AVL Tree

AVL Tree란?

AVL 트리는 트리를 구성하는 모든 노드들에 대하여 각 노드의 왼쪽 서브 트리 높이와 오른쪽 서브 트리 높이의 차이가 최대 1을 넘지 않는 Binary Search Tree입니다. 즉 편향 트리가 되지 않도록 트리 높이의 균형을 유지하는 트리입니다.

Red-Black Tree보다 균형을 더 엄격하게 유지하기 때문에 더 빠른 탐색 성능을 가지지만 삽입, 삭제 시 균형 유지를 위한 더 많은 작업이 필요합니다.

Operation

AVL 트리의 탐색 연산은 이진 탐색 트리와 동일하며 삽입, 삭제 연산은 이진 탐색 트리의 삽입, 삭제 연산에 트리의 균형 유지를 위한 작업이 추가된 형태입니다.

연산을 수행하고 트리의 불균형이 발견된다면 회전을 통해 균형을 맞춥니다.

  • LL Rotation
  • RR Rotation
  • LR Rotation
  • RL Rotation

트리의 균형을 맞추기 때문에 AVL 트리의 높이는 O(log n) 이며 따라서 AVL 트리의 탐색, 삽입, 삭제 연산은 O(log n) 의 시간복잡도를 갖습니다.

Red-Black Tree

Red-Black Tree란?

레드 블랙 트리는 트리 높이의 균형을 맞추기 위해 다음 4가지 속성을 만족하도록 한 Binary Search Tree입니다.

  • Root Property: 루트 노드는 블랙 노드
  • External Property: 모든 Leaf node (NIL)는 블랙 노드
  • Internal Property: 레드 노드의 자식 노드는 블랙 노드
  • Depth Property: 모든 잎들은 같은 Black Depth를 가짐

    Black Depth: Leaf node 에서 Root node 까지 가는 동안 만나는 블랙 노드의 수

AVL Tree보다 균형을 덜 엄격하게 유지하기 때문에 상대적으로 느린 탐색 성능을 가지지만 삽입, 삭제는 더 빠릅니다.

레드 블랙 트리는 C++ STL SetMap을 구현하는데 사용됩니다.

Operation

레드 블랙 트리의 탐색 연산은 이진 탐색 트리와 동일하며 삽입, 삭제 연산은 이진 탐색 트리의 삽입, 삭제 연산에 레드 블랙 트리 속성 조건을 만족시키기 위한 작업이 추가된 형태입니다.

트리의 균형을 맞추기 때문에 레드 블랙 트리의 높이는 O(log n) 이며 따라서 레드 블랙 트리의 탐색, 삽입, 삭제 연산은 O(log n) 의 시간복잡도를 갖습니다.

profile
안드로이드 개발자를 꿈꾸는 사람

0개의 댓글