예제가 포함된 이진 검색 트리(BST)

이진 검색 트리란 무엇입니까?

이진 검색 트리(BST)는 노드와 그 노드의 좌우 분기를 트리 구조로 모델링하여 분석하고 값을 반환하는 고급 알고리즘입니다. BST는 기본적인 이진 검색 알고리즘의 아키텍처를 기반으로 설계되었기 때문에 노드 검색, 삽입 및 삭제 속도가 매우 빠릅니다. 따라서 프로그램의 속도와 정확도가 크게 향상됩니다.

이진 검색 트리의 속성

BST는 여러 노드로 구성되며 다음과 같은 속성으로 구성됩니다.

• 트리의 노드들은 부모-자식 관계로 표현됩니다.
• 각 상위 노드에는 하위 노드가 없거나 왼쪽과 오른쪽에 최대 XNUMX개의 하위 노드 또는 하위 트리가 있을 수 있습니다.
• 이진 검색 트리라고도 알려진 모든 하위 트리에는 오른쪽과 왼쪽에 하위 가지가 있습니다.
• 모든 노드는 키-값 쌍으로 연결됩니다.
• 왼쪽 서브트리에 있는 노드들의 키는 해당 부모 노드의 키보다 작습니다.
• 마찬가지로, 오른쪽 서브트리에 있는 노드들의 키는 해당 부모 노드의 키보다 큽니다.

1. 가장 상위 노드 또는 부모 레벨 11이 있습니다. 그 아래에는 각각 고유한 키 값을 가진 좌측 및 우측 노드/분기가 있습니다.
2. 오른쪽 하위 트리의 키 값이 부모 노드보다 큽니다.
3. 왼쪽 하위 트리의 키 값이 부모 노드보다 작습니다.

이진 검색 트리가 필요한 이유는 무엇입니까?

• 이진 탐색 트리가 실제 문제에 대한 최적의 해결책이 되는 두 가지 주요 요인은 속도와 정확성입니다.
• 이진 검색은 부모-자식 관계가 있는 가지와 같은 형식이기 때문에 알고리즘은 요소를 검색해야 하는 트리의 어느 위치에서인지 알고 있습니다. 이렇게 하면 프로그램이 원하는 요소를 찾기 위해 수행해야 하는 키-값 비교 횟수가 줄어듭니다.
• 또한, 검색 대상 요소의 크기가 부모 노드보다 크거나 작을 경우, 해당 노드는 어느 트리 쪽을 검색해야 하는지 알 수 있습니다. 그 이유는 왼쪽 서브트리는 항상 부모 노드보다 작고, 오른쪽 서브트리는 항상 부모 노드와 같거나 큰 값을 가지기 때문입니다.
• BST는 일반적으로 복잡한 검색, 견고한 게임 로직, 자동 완성 활동 및 그래픽을 구현하는 데 사용됩니다.
• 이 알고리즘은 검색, 삽입, 삭제와 같은 작업을 효율적으로 지원합니다.

이진 트리 유형

세 가지 종류의 이진 트리는 다음과 같습니다.

• 완전 이진 트리: 트리의 모든 레벨이 가득 차 있으며, 마지막 레벨만 예외일 수 있습니다. 마찬가지로 모든 노드가 가득 차 있으며, 맨 왼쪽을 가리키고 있습니다.
• 완전한 이진 트리: 리프 노드를 제외한 모든 노드는 자식 노드를 2개씩 가지고 있습니다.
• 균형 이진 트리 또는 완벽한 이진 트리: 트리에서 모든 노드는 두 개의 자식을 가지고 있습니다. 또한, 각 서브노드는 동일한 레벨을 가집니다.

더 많은 내용을 확인하세요. 데이터 구조의 이진 트리 당신이 관심이 있다면.

이진 검색 트리는 어떻게 작동하나요?

트리는 항상 루트 노드와 추가 자식 노드를 가지며, 이는 왼쪽이든 오른쪽이든 상관없습니다. 알고리즘은 루트와 그에 따른 왼쪽 또는 오른쪽 서브 트리의 추가 자식 노드와 값을 비교하여 모든 연산을 수행합니다.

삽입, 검색 또는 삭제할 요소에 따라 비교 후 알고리즘은 루트 노드의 왼쪽 또는 오른쪽 서브트리를 쉽게 삭제할 수 있습니다.

BST는 기본적으로 다음 세 가지 유형의 작업을 사용할 수 있도록 제공합니다.

• 수색: 이진 트리에서 해당 요소를 검색합니다.
• 삽입 : 이진 트리에 요소를 추가합니다.
• 지우다: 이진 트리에서 요소를 삭제합니다.

각 작업에는 고유한 구조와 실행/분석 방법이 있지만, 가장 복잡한 작업은 삭제 작업입니다.

검색 Opera기

트리 분석은 항상 루트 노드에서 시작하여, 찾고자 하는 요소가 루트 노드보다 작은지 큰지에 따라 루트 노드의 오른쪽 또는 왼쪽 서브트리로 이동하면서 진행해야 합니다.

1. 찾을 요소는 10입니다.
2. 해당 요소를 루트 노드 12와 비교하면 10 < 12이므로 왼쪽 서브트리로 이동합니다. 오른쪽 서브트리는 분석할 필요가 없습니다.
3. 이제 10을 노드 7과 비교해 보면 10 > 7이므로 오른쪽 서브트리로 이동합니다.
4. 그다음 10을 다음 노드인 9와 비교합니다. 10 > 9이므로 오른쪽 하위 트리의 자식 노드를 확인합니다.
5. 10은 노드의 값과 일치하고 10 = 10이며 사용자에게 값을 반환합니다.

별명 Code 영국 서머타임(BST) 검색용

search(element, root)
    if !root
        return -1
    if root.value == element
        return 1
    if root.value < element
        search(element, root.right)
    else
        search(element, root.left)

끼워 넣다 Opera기

이 작업은 매우 간단합니다. 먼저 루트 노드를 삽입하고, 그 다음 값을 루트 노드와 비교합니다. 값이 루트보다 크면 오른쪽 서브트리에 추가하고, 루트보다 작으면 왼쪽 서브트리에 추가합니다.

1. 왼쪽에서 오른쪽 순서대로 이진 검색 트리(BST)에 삽입해야 하는 요소 6개의 목록이 있습니다.
2. 루트 노드로 12를 삽입하고, 다음 값인 7과 9를 비교하여 각각 오른쪽 및 왼쪽 서브트리에 삽입합니다.
3. 나머지 값 19, 5, 10을 루트 노드 12와 비교하여 적절하게 배치합니다. 19 > 12이므로 12의 오른쪽 자식으로 배치하고, 5 < 12이고 5 < 7이므로 7의 왼쪽 자식으로 배치합니다. 이제 10을 비교해 보면, 10은 12보다 작고 7보다 크며 9보다 크므로 9의 오른쪽 서브트리로 배치합니다.

BST에 노드를 삽입하기 위한 의사 코드

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
        y = x
        if x.value < element.value
            x = x.right
        else
            x = x.left
    if y.value < element
        y.right = element
    else
        y.left = element

. OperaTIONS

이진 검색 트리(BST)에서 노드를 삭제할 때는 루트 노드를 삭제하는 경우와 리프 노드를 삭제하는 경우 등 몇 가지 경우가 있습니다. 또한, 루트 노드를 삭제한 후에는 루트 노드에 대해 다시 한번 생각해 봐야 합니다.

리프 노드를 삭제하고 싶다면 그냥 삭제하면 되지만 루트를 삭제하고 싶다면 루트의 값을 다른 노드로 바꿔야 합니다. 다음 예를 들어보겠습니다.

• 사례 1 – 자식 노드가 없는 노드: 이것은 가장 간단한 상황입니다. 오른쪽이나 왼쪽에 더 이상 자식 노드가 없는 노드를 삭제하기만 하면 됩니다.
• 사례 2 – 자식 노드가 하나인 노드: 노드를 삭제한 후에는 해당 노드의 자식 노드를 삭제된 값의 부모 노드에 연결하기만 하면 됩니다.
• 사례 3 – 자식 노드가 두 개인 노드: 이것이 가장 어려운 상황이며, 다음 두 가지 규칙에 따라 작동합니다.
  • 3a – 순차적 선행 요소: 자식 노드가 두 개인 노드를 삭제하고, 삭제된 노드의 왼쪽 서브트리에서 가장 큰 값으로 대체해야 합니다.
  • 3b – 순차적 후속자: 자식 노드가 두 개인 노드를 삭제하고, 삭제된 노드의 오른쪽 하위 트리에서 가장 작은 값으로 대체해야 합니다.

1. 이는 자식이 없는 노드를 삭제하는 첫 번째 사례입니다. 그림에서 볼 수 있듯이 19, 10, 5는 자식이 없습니다. 하지만 우리는 19를 삭제할 것입니다.
2. 값 19를 삭제하고 노드에서 링크를 제거합니다.
3. 19를 제외한 BST의 새로운 구조를 확인하세요.

1. 이는 자식 노드가 하나만 있는 노드를 삭제하는 두 번째 삭제 사례입니다. 그림에서 볼 수 있듯이 노드 9는 자식 노드가 하나 있습니다.
2. 노드 9를 삭제하고 자식 노드 10으로 교체한 다음, 노드 7에서 노드 10으로 링크를 추가합니다.
3. 9를 제외한 BST의 새로운 구조를 확인하세요.

1. 여기서는 자식 노드가 두 개 있는 노드 12를 삭제합니다.
2. 노드 삭제는 중위 순서 선행 노드 규칙에 따라 이루어지며, 이는 노드 12의 왼쪽 서브트리에서 가장 큰 요소가 해당 노드를 대체한다는 것을 의미합니다.
3. 노드 12를 삭제하고 왼쪽 서브트리에서 가장 큰 값인 10으로 교체합니다.
4. 12를 삭제한 후의 BST의 새로운 구조를 확인하세요.

1. 자식 노드가 두 개 있는 노드 12를 삭제합니다.
2. 해당 노드의 삭제는 중위 순서 후속 노드 규칙에 따라 이루어지며, 이는 12번 노드의 오른쪽 하위 트리에서 가장 작은 요소가 해당 노드를 대체한다는 의미입니다.
3. 노드 12를 삭제하고 오른쪽 서브트리에서 가장 작은 값인 19로 교체하십시오.
4. 12를 삭제한 후의 BST의 새로운 구조를 확인하세요.

별명 Code 노드 삭제를 위해

delete (value, root):
    Node x = root
    Node y = NULL
    # searching the node
    while x:
        y = x
        if x.value < value
            x = x.right
        else if x.value > value
            x = x.left
        else if value == x
            break
    # if the node is not null, then replace it with successor
    if y.left or y.right:
        newNode = GetInOrderSuccessor(y)
        root.value = newNode.value
        # after copying the value of successor, delete the successor
        free(newNode)
    else
        free(y)

중요한 용어

• 삽입 : 트리에 요소를 삽입하거나 트리를 생성합니다.
• 수색: 트리 구조에서 요소를 검색합니다.
• 전위 순회: 트리를 전위 순회합니다.
• 중위 순회: 트리를 중위 순회합니다.
• 후위 순회: 후위 순회 방식으로 트리를 탐색합니다.

자주 묻는 질문