이진 탐색 트리 (BST,Binary Search Tree)

규칙

• 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 의 형태를 가진 이진 트리
• 각각의 서브트리도 위의 규칙을 유지
• 중복된 키 허용 X

이진 탐색 트리

특징

• 데이터가 정렬되어 이진 트리에 비해 탐색이 빠름 (대신 균형 유지가 필요하다)
  • 균형 상태 : O(logN)
  • 불균형 상태 : O(N)  -> 한쪽으로 편향되어 있는 경우
• In-order 순회를 하면 오름차순으로 된다.

 

탐색 (Search)

• 찾고자 하는 데이터를 root 노드부터 대소 비교
  
  • 데이터가 작으면 왼쪽 이동
  • 데이터가 크면 오른쪽 이동
• 찾는 데이터가 없으면 null 반환
• 어떤 데이터를 찾더라도 최대 트리의 높이 만큼의 탐색이 이루어짐

 

삽입 (Insert)

• 균형 고려하지 않을 시
  • 삽입할 데이터를 root 노드부터 비교 (search와 동일)
  • leaf 노드에 도달 후, 작으면 왼쪽 , 크면 오른쪽에 삽입
  • 중복 키 발견 시 노드 추가하지 않고 종료ㅁ

 

삭제 (Delete)

• 삭제 대상 노드가 Leaf인 경우
  • 삭제 대상 노드 삭제
  • 부모 노드의 해당 자식 링크 null로 변경
• 자식 노드가 하나 있는 경우
  • 자식 노드를 삭제 대상 노드의 부모노드에 연결
  • 삭제 대상 노드 삭제
• 자식 노드가 둘인 경우
  • 삭제 대상 노드의 왼쪽 서브 트리에서 가장 큰 노드 or 오른쪽 서브트리에서 가장 작은 노드 선택
    • 전자의 경우, 왼쪽으로 한 번 간뒤 오른쪽으로 쭉 내려가면 가장 큰 노드
    • 후자의 경우, 오른쪽으로 한 번 간뒤 왼쪽으로 쭉 내려가면 가장 작은 노드
  • 선택한 노드를 삭제 대상 노드의 위치로 올림
  • 올리면서 다른 자식 노드들의 링크 연결 작업
  • 삭제 대상 노드 삭제

---

균형 이진 탐색 트리 (Balanced Binary Search Tree)

• 모든 노드의 좌우 서브 트리 높이가 1 이상 차이 나지 않는 이진 탐색트리
• 노드의 삽입과 삭제 시에도 균형을 유지하도록 하는 트리
  • 이진 트리는 삽입 및 삭제가 편향적으로 일어나 탐색 속도가 최악인 O(logN) 모양의 편향트리가 될 수 있다.
  • 이를 막기 위해 삽입,삭제 시 균형을 유지할 필요가 있다. 
• 종류
  • AVL Tree 
  • Red - Black Tree

---

​AVL Tree

• 노드가 삽입, 삭제될 때 트리의 균형을 체크하고 유지하는 트리
• 각 노드의 BF를 [-1, 0, 1] 만 가지게 하여 균형을 유지
  • BF (Balanced Factor) = 왼쪽 서브 트리 높이(hL) - 오른쪽 서브 트리 높이(hR)

AVL Tree의 리밸런싱

• 균형이 깨진 경우
  • BF 가 + 이면 왼쪽 서브트리에 이상
  • BF 가 - 이면 오른쪽 서브트리에 이상
• 회전 연산을 통해 리밸런싱
  • 단순 회전 : LL , RR
  • 이중 회전 : LR, RL

 

LL (Left - Left) 

• 오른쪽 방향으로 회전 1회

 

RR (Right - Right)

• 왼쪽 방향으로 회전 1회

LR (Left - Right)

• RR 회전 후, LL 회전

RL (Right - Left)

• LL 회전 후 , RR 회전

---

Red - Black Tree

• 조건
  • root 노드와 leaf 노드의 색은 black
  • red 색 노드의 자식은 black (red는 연속적으로 나올 수 없다)
  • 모든 leaf 노드(NIL 노드)에서 root 노드 까지 가는 경로 상의 black 노드 수는 모두 같다
  • 조건이 깨지면 리밸런싱

삽입

트리에 노드를 추가할 땐 무조건 red로 추가, 그 후 상황에 따라 조정

• 노드 삽입 후 double red 발생
  • 부모 노드의  형제가 red일 때 -> Recoloring 진행
    •  부모와 부모의 형제 노드를 black으로 변경
    • 부모의 부모 노드를 red로 변경
    • 부모의 부모 노드가 root인지 double red 인지에 따라  조정 진행 
  • 부모 노드의 형제가 없거나, black일 때 -> Restructuring 진행
    • 조정 대상 : 삽입한 노드 , 부모 노드, 부모의 부모 노드
    • 조정 대상을 오름차순 정렬
    • 가운데 노드를 부모 노드로 선정 및 black 변경
    • 나머지 두 노드를 자식 노드로 두고 red 변경

삭제

• 삭제 대상 노드가 black이고 그 자리에 오는게 red 일 경우
  • 해당 자리로 오는 red를 black으로 변경
• 삭제 대상 노드가 black이고 그 자리에 오는게 black 일 경우 (이중 흑색)
  • 이중 흑색 노드의 형제 노드가 black 이고 형제의 양쪽 자식이 모두 black인 경우
    • 형제 노드를 red로 변경
    • 이중 흑색 노드의 검은색 1개를 부모로 전달
    • 부모가 root이 아닌 이중 흑색 노드가 되면 다시 해당 case 반복
  • 이중 흑색 노드의 형제 노드가 red인 경우
    • 형제 노드를 black으로 변경
    • 부모 노드를 red로 변경
    • 부모 노드를 기준으로 왼쪽으로 회전
    • 그 다음 이중 흑색 case에 따라 반복

출처 : zero-base

• 이중 흑색 노드의 형제 노드가 black이고 오른쪽 자식이 red인 경우
  • 부모 노드와 형제 노드의 오른쪽 자식 노드를 검은색으로 변경
  • 부모 노드를 기준으로 왼쪽으로 회전
• 이중 흑색 노드의 형제 노드가 black이고 왼쪽 자식이 red인 경우
  • 형제 노드를 red로 변경
  • 형제 노드의 왼쪽 자식 노드를 black으로 변경
  • 형제 노드를 기준으로 왼쪽으로 회전
  • 위의 case를 진행

 

Red - Black VS AVL

• 알고리즘 시간 복잡도 : 둘 다 O(logN)
• 균형 수준 : AVL 트리가 좀 더 엄격하게 균형 잡음, 대신 Red-Black은 색으로 구분하기 때문에 회전 수가 감소
• 실 사용 시 : 탐색이 많은 경우는 AVL  /  삽입,삭제가 많은 경우는 Red-Black
• 현실에서는 삽입,삭제가 빈번하게 일어나는 경우가 많으므로 Red-Black을 좀 더 많이 사용한다