[5주차] 이진 탐색 트리

[ella-yschoi]

이진 탐색 알고리즘의 개념을 기반으로 동적 자료 구조를 생성하는 BST를 알아봅시닷

[hanana1253]

이진 탐색 트리 (Binary Search Tree)

요약

• 동적 자료 구조 생성
• 정렬된 배열과 달리, 효율적인 원소 추가와 제거 뿐 아니라 탐색도 지원하므로 이진 탐색 알고리즘적 효율성과 동적 자료구조의 적응성 결합

1. 이진 탐색 트리 구조

• 트리: 노드의 분기 사슬로 구성된 계층적인 자료 구조
• 노드: 값을 포함하며, 트리의 하위 노드를 가리키는 포인터를 최대 두 개 가진다
  • 내부(internal) 노드: 자식이 하나 이상
  • 단말(terminal)/leaf/종단 노드: 어떤 자식도 없는 노드
  • 부모에 대한 포인터 등 선택적으로 부가 데이터 저장 가능
• 루트: 뿌리 노드로, 단 하나의 포인터를 사용해 이진 탐색 트리에 접근

2. 이진 탐색 트리에서 탐색하기

• 현재 노드의 값과 목푯값을 비교해 탐색 방향 결정
• 목푯값을 발견하거나, 더 이상 자식이 없는 노드에 도달하면 종료(목푯값이 트리에 없음)
• 반복이나 재귀를 사용해 구현 가능하며, 계산 비용은 트리에서 목푯값을 찾는 데 필요한 깊이에 비례
• 트리 깊이를 최소화해서 탐색 효율성을 높이는 것이 중요
• 트리를 만드는 비용이 선형 스캔을 한 번 진행(특히 정렬된 배열이라면)하는 것보다 더 비싸지만, 데이터가 동적으로 변경되는 경우 트리 구조와 탐색 방법의 트레이드오프가 달라진다.
  • 데이터를 효율적으로 추가하거나 제거할 수 있다. (c.f. 정렬된 배열에서는 데이터를 추가하거나 제거할 때마다 매번 배열 갱신)

3. 이진 탐색 트리 변경하기

• 루트 노드를 통해 트리가 비어있는지 확인
• 삽입: 탐색과 같이 트리를 따라 이동하다가 막다른 골목에서 새 노드 추가, 최악의 경우 삽입 비용은 트리의 깊이에 선형적으로 비례하여 증가
• 제거
  • 자식이 없는 리프 노드를 제거하는 경우, 그냥 제거
  • 자식을 하나만 가진 경우, 자식을 제거된 노드의 부모의 자식으로 승격시키고 제거
  • 자식이 둘인 노드를 제거하려면 제거할 노드를 제외한 나머지 트리의 무결성을 유지하고 계속 이진 탐색 트리 속성을 따르도록 보장해야 한다.
    • 제거할 노드의 후속자(successor, 정렬된 순서로 노드를 순회할 때 제거할 노드 바로 다음에 만나게 될 노드)를 찾아 후속자의 값을 제거된 노드 위치에 넣고, 후속자를 찾아 후속자를 가리키는 포인터를 저장한 다음, 후속자를 트리에서 제거
  • 제거 또한 최악의 경우 트리의 깊이에 선형적으로 비례하는 실행 시간이 소요된다

4. 균형이 맞지 않는 트리의 위험성

• 완전 균형 트리: 모든 노드에서 오른쪽 하위 트리가 왼쪽 하위 트리와 동일한 수의 노드를 포함하는 경우
• 트리 깊이가 노드 수를 두배로 늘릴 때마다 1씩 증가.
• 트리가 균형이 잘 맞지 않으면 트리 깊이가 선형적으로 증가하며, 정렬된 연결 리스트에 지나지 않을 수도 있다.

5. 이진 탐색 트리 대량 구축 (Bulk Construction)

• 값으로 이뤄진 집합이 주어졌을 때, 이 초기 집합으로부터 균형잡힌 이진 탐색 트리를 구축
• 각 단계에서 중앙값을 그 깊이의 노드로 선택

6. 이진 탐색 트리가 중요한 이유

• 동적 자료 구조를 구체적 문제에 적용하는 방법을 보여준다.

느낀 점

• 유머 감각이 지표가 되는 홍보 부서...? 멀쩡한 예시는 없는 걸까...? 갑자기 커피 예시가 굉장히 노말하게 들리기 시작했다.
• 이번 챕터에서 책이 초심을 좀 잃을 뻔 한 것 같다. 주의해주세요.
• 트라이는 예전에 이해 못했던 자료구조인데 다음 챕터라니 기대가 되는군

[sunhpark42]

전 그런 부서라면 10번쯤에 있을거 같아요.. 한결님은 80번대 이상이 분명

[ella-yschoi]

정리

"노드 값은 마치 호텔 객실을 찾아갈 때 500-519호실이 왼쪽에 있고, 520-590호실이 오른쪽에 있음을 알려주는 표지판과 같다"

• 위 문장이 이진 탐색 트리를 설명하는 찰떡 비유라 생각했습니다.
• 반복적 탐색과 재귀적 탐색으로 나누어 트리를 탐색/구현할 수 있어 좋았습니다.
• 두 자식을 가진 내부 노드를 제거하기 위해 먼저 후속자 노드를 해당 위치로 교환하는 로직이 재밌었어요.

[ainochi-kor]

정리

: 이진 탐색 트리를 이해하는데 정말 좋았다고 생각합니다. 이진 트리를 구성할 때의 방식에 대해서 고민해보지 않았는데 트리를 구성하는 방법을 배워서 한번 적용해보면 좋을 것 같다고 생각하였습니다.

[yunseorim1116]

정리
해놓고 올리는걸 잊어버릴뻔했던..
원래 알고리즘도 같이 풀어보고싶었는데 이번주는 몸이 안좋아서 책을 읽기만 한게 아쉬웠네요 ㅠ
책 내용은 너무 좋았고 글로 풀어서 잘 설명해줘서 구현하면서 한번 더 익혀보고싶습니다 !

[hanana1253]

서림님 아프지마세영

[ddongule]

아프지마라 당신!!!!!

[thgr8ganzi]

정리

• 간단할줄 알았던, 생각보다 오래걸린 이진탐색 트리
• 실제로 코드를 써내려가 보는것에서 이전보다 좀 더 오래 기억에 남을것 같습니다.

[sunhpark42]

• 여행중이라 전자책 하이라이트 사진으로 올립니다
• 책을 읽을수록 대학생때 왜 그리 자료구조가 어려웠을까 싶었는데, 해결하고자 하는 문제가 무엇인지 명확히 파악하고 정의하지 않았기 때문이었다는 것을 깨달았다. 해결하고자 하는 문제를 이해하지 못했으니, 해결을 위한 도구가 이해가지 않는건 당연한게 아니었을까🙃

[sunhpark42]

다들 적게 일하고 많이버는 2025 되십셔~~!

[hanana1253]

오예~~ 적일많벌!!!

[sa02045]

정리

• 이진탐색트리 정적인 배열보다 동적인 데이터를 다룰 때 훨씬 유리함
• 이진탐색트리 추가, 삭제 방법을 익혔습니다
• 삭제 알고리즘이 자식의 갯수 경우에 따라서 복잡한데, 알고리즘의 기본을 복습하고 익히는데 좋은 예시인것 같아요

[ddongule]

항상 이런 자료구조 얘기가 나오면 뭔얘기지 하고 지나쳤던 것 같은데 이번에 이진 탐색 트리에 대해 죄금이나마 감이 잡혀가능 것 같아 기분이 좋씁니다..
왜 오늘이 일요일이죠 왜..?ㅎ.. 벌써 내일 퇴근하고싶어요..
유머 수준에 따라 구성된 홍보부서에 저도 입사하고싶어요 이런 비유는 어떻게 생각하는거죠?;;
래퍼 함수를 보면 자꾸 오겜 타노스가 생각나요;; 흔한 ADHD의 책읽기랄까..
이진 트리의 탐색이랑 삽입까지는 괜찮았는데 자식이 둘인 내부 노드를 제거하는걸 볼 때에는 살짝 현기증이났어요
후속자를 찾는걸 이해하는게 어려웠는데.. 오른쪽 하위 트리의 최소는 그냥 저자가 말한 예시 중 하나겠쬬?
왼쪽 하위 트리의 최대도 되지 않나 싶어서..^^ 혹시 제가 이해하지 못하는 부분이있다면 아무나 알려주십시요.. 깔깔!!!!!!!!!

[sa02045]

트리를 재조정하는 작업이 복잡하져서 오른쪽 하위 트리의 최소로 후속자를 정하는 것 같아요! (왼쪽 하위 트리의 최대도 되긴 된다)

왼쪽 하위 트리의 최대를 후속자로 하면 좀 더 신경써야할게 많은 느낌?(후속자 노드의 자식노드를 고민해야함)

         50
        /  \
      30    70
     /  \
   20   40
       /
     35

• 50을 삭제하려면 40으로 대체해야하는데 40의 자식인 35를 고려해야함..

[thgr8ganzi]

• 중위 후속자(in-order successor) -> 오른쪽에 가장 작은 값
• 중위 선행자(in-order predecessor) -> 왼쪽에서 가장 큰 값

---

• gpt 답변

중위 후속자와 중위 선행자 모두 이진 탐색 트리의 속성을 유지하면서 노드를 삭제하는 데 사용할 수 있습니다. 중위 후속자를 더 자주 추천하는 이유는 다음과 같습니다:

1. 관례: 많은 교과서와 알고리즘 자료에서 중위 후속자를 사용하는 방법을 더 자주 소개합니다. 이는 단순히 관례적인 선택일 수 있습니다.
2. 구현의 일관성: 오른쪽 서브트리에서 가장 작은 값을 찾는 것이 왼쪽 서브트리에서 가장 큰 값을 찾는 것보다 구현이 더 간단할 수 있습니다.
3. 캐시 효율성: 일부 시스템에서는 오른쪽으로 이동하는 것이 캐시 효율성 측면에서 더 유리할 수 있습니다.
4. 특정 응용 프로그램의 요구사항: 일부 응용 프로그램에서는 후속자를 사용하는 것이 더 자연스러울 수 있습니다.

그러나 실제로는 중위 후속자와 중위 선행자 중 어느 것을 사용해도 이진 탐색 트리의 속성과 성능에 큰 차이가 없습니다. 따라서 특별한 이유가 없다면 둘 중 어느 방법을 사용해도 무방합니다.

생각지도 못했는데 그랫군요

[ddongule]

오우~!!!! 두분 다 답변 감사합니다!!!!!!! > <

[iborymagic]

• 이진탐색트리까지는 항상 재미있게 읽었던 것 같습니다.. 다음주가 두렵네요
• 삭제 알고리즘이 제일 복잡한데, 다시 읽으면서 내용을 좀 정리해봐야겠읍니다.. 다음에 배울 자료구조들에서도 뭔가 응용될 만한 내용인 것 같아서요..
• 예시가 이상합니다.. 호텔방 예시는 좋았는데 유머 부서는 도대체 뭔지 허허 집중력이 떨어지는 예시였읍니다..
• 다시 읽고 정리한 내용도 올려보겠읍니다..

---

• 이진탐색트리 = 이진 탐색 개념을 기반으로한 동적 자료구조
• 트리 = 노드의 분기 사슬로 구성된 계층적 자료구조

[탐색]

• 이진탐색트리의 탐색은 루트노드에서 시작, 목푯값과 비교를 통해 반쪽 트리 전체를 제거하면서 시작
  • 이진탐색 알고리즘의 '가지치기'와 동일
  • 오른쪽 가지를 탐색할 때마다 탐색 공간의 하계를 증가, 왼쪽 가지를 탐색할 때마다 탐색 공간의 상계를 감소
  • 트리를 내려가면서 현재 노드가 목푯값과 동일하면 탐색 조기 종료
  • 트리가 깊을수록 더 많이 비교해야하므로, 트리 깊이를 최소화해서 탐색 효율성을 높여야함
• 데이터가 동적인 경우에는 정렬된 배열로 처리할 때 부가 비용이 커짐
  • 이런 경우에는 동적 자료 구조인 이진탐색트리를 사용하면 데이터를 효율적으로 추가/제거 가능

[삽입]

• 탐색과 기본적으로 동일한 알고리즘을 사용
• 탐색과 삽입의 주된 차이는, 삽입은 막다른 골목에 도달한 후 현재 노드의 자식으로 새 노드를 추가
• 중복값을 허용하면, 막다른 골목에 도달했을 때 새 값을 트리에 삽입
• 중복값을 허용하지 않으면, 새 값과 일치하는 노드에 저장된 데이터를 대체하거나 추가 정보를 저장
• 새 노드를 트리에 삽입하는 비용은 새 노드를 삽입하는 경로의 깊이에 비례
• 최악의 경우 삽입 비용은 트리의 깊이에 선형적 비례

[제거]

• 노드를 제거할 때는 세 가지 경우를 고려해야함
• 자식이 없는 리프 노드를 제거하는 경우
  • 해당 노드를 제거하고, 부모의 자식 포인터를 null로 갱신
• 자식을 하나만 가진 노드를 제거하는 경우
  • 해당 자식을 제거된 노드의 부모의 자식으로 승격시키고, 제거 대상 노드를 제거한다
• 자식 노드가 둘인 내부 노드를 제거하는 경우
  • 제거할 노드를 제외한 나머지 트리의 무결성을 유지하고, 계속 이진탐색트리의 속성을 따르게 보장해야함
  • 제거할 노드와 교환해도 나머지 트리의 속성이 유지될 수 있는 '후속자'를 찾아야함
  • 후속자 = 오른쪽 하위 트리의 최소 노드

[균형이 맞지 않는 트리의 위험성]

• 완전 균형 트리에서 최악의 경우 탐색/삽입/제거의 성능은 log(2)N에 비례해 증가
• 극단적으로 균형이 맞지 않는 경우, 이진탐색트리는 정렬된 연결 리스트에 지나지 않을 수 있음
  • 이 경우, 작업 시간은 N에 선형적으로 비례
• 동적 삽입, 제거가 발생하는 동안 트리의 균형을 유지하기 위해 레드블랙 트리, 2-3트리, B-트리 등이 존재
  • 해당 접근 방법들은 균형을 유지하는 대신 트리 연산의 복잡도가 증가
• 값 집합이 주어졌을 때, 균형 잡힌 이진탐색트리를 구축하는 간단한 방법 = 대량 구축
• 대량구축 = 배열의 중간 원소를 새 노드로 만든 후, 재귀적으로 더 작은 부분집합으로 나누면서 이진탐색트리를 생성

[chloe-codes1]

내용 정리

이진 탐색 트리 구조

• 트리는 노드가 여러 갈래로 분기하는 계층적 자료 구조다
• 연결 리스트에서 각 노드는 하나의 다음 노드만 가리키지만, 트리의 노드는 여러 자식 노드를 가리킬 수 있다
• 이진 트리는 각 노드가 최대 2개의 자식을 가질 수 있다
• 노드에 부모 포인터를 저장하면 탐색이나 노드 제거 같은 연산에서 유용하다
• 모든 노드 N에 대해,
  • N의 왼쪽 하위 트리에 속한 모든 노드의 값은 N의 값보다 작으며,
  • N의 오른쪽 하위 트리에 속한 모든 노드의 값은 N의 값보다 크다
• 노드 값은 큰 범위를 왼쪽, 작은 범위를 오른쪽(또는 그 반대)으로 구분하는 표지판 역할을 한다

이진 탐색 트리에서 탐색하기

• 반복적 탐색(Iterative)

  • 설명

    • while 루프를 사용해 트리를 내려가며 탐색한다

  • 장점

    • 스택을 사용하지 않아 메모리를 효율적으로 쓸 수 있다

  • e.g.

    from __future__ import annotations
    from typing import Optional
    
    class TreeNode:
        def __init__(self, value: int) -> None:
            self.value = value
            self.left: Optional[TreeNode] = None
            self.right: Optional[TreeNode] = None
    
    def insert_node_iterative(root: Optional[TreeNode], value: int) -> TreeNode:
        if root is None:
            return TreeNode(value)
    
        current = root
        while True:
            if value < current.value:
                if current.left is None:
                    current.left = TreeNode(value)
                    break
                current = current.left
            else:
                if current.right is None:
                    current.right = TreeNode(value)
                    break
                current = current.right
        return root
    
    def iterative_search(root: Optional[TreeNode], value: int) -> bool:
        current = root
        while current:
            if current.value == value:
                return True
            current = current.left if value < current.value else current.right
        return False

• 재귀적 탐색(Recursive)

  • 설명

    • 함수가 자신을 호출하는 구조

  • 장점

    • 간결한 코드

  • 단점

    • 트리가 깊을 경우 스택 오버플로우 위험이 있다

  • e.g.

    def insert_node_recursive(root: Optional[TreeNode], value: int) -> TreeNode:
        if root is None:
            return TreeNode(value)
        if value < root.value:
            root.left = insert_node_recursive(root.left, value)
        else:
            root.right = insert_node_recursive(root.right, value)
        return root
    
    def recursive_search(root: Optional[TreeNode], value: int) -> bool:
        if root is None:
            return False
        if root.value == value:
            return True
        if value < root.value:
            return recursive_search(root.left, value)
        else:
            return recursive_search(root.right, value)

이진 탐색 트리 변경하기

• 이진 탐색 트리를 감싸는 간단한 자료 구조(wrapper)를 사용하면 루트 노드 처리를 단순화할 수 있다
• 노드를 삽입할 때는 탐색과 같은 로직을 따라가며, 중복 허용 여부에 따라 처리 방식이 달라진다
• 노드를 제거할 때는 노드가 리프인지, 자식이 하나인지, 두 개인지에 따라 제거 방식이 달라진다
• 두 자식을 가진 노드를 제거하려면 후속자(successor) 노드와 교환 후 제거하는 과정을 거친다

균형이 맞지 않는 트리

• 트리가 완전히 균형을 이룰 경우 노드 수가 2배로 늘어날 때마다 트리 깊이는 1씩만 증가해 대략 O(log N) 성능을 낸다
• 균형이 무너진 트리는 삽입·삭제를 반복할 때 깊이가 선형적으로 늘어나 O(N)까지 성능이 떨어질 수 있다
• 균형을 유지하려면 red-black 트리처럼 추가 규칙을 도입해야 하며, 이로 인한 연산 복잡도 증가라는 대가가 따른다

이진 탐색 트리 대량 구축

• 반복 삽입으로 트리를 만들면 균형이 깨질 위험이 있다
• 정렬된 배열에서 중간 요소를 루트로 잡고, 왼쪽/오른쪽 서브트리에 대해 재귀적으로 같은 작업을 수행하면 균형 잡힌 이진 탐색 트리를 만들 수 있다

생각

이제 다음주가 어려워질 것 같다! 화이팅!