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

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

이진 탐색 트리는 노드, 왼쪽 및 오른쪽 브랜치를 분석하는 데 사용되는 고급 알고리즘으로, 트리 구조로 모델링되어 값을 반환합니다. BST는 기본 이진 탐색 알고리즘의 아키텍처에 따라 고안되었으므로 노드의 빠른 조회, 삽입 및 제거가 가능합니다. 이를 통해 프로그램이 정말 빠르고 정확해집니다.

이진 검색 트리의 속성

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

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

기본 노드 또는 상위 수준 11이 있습니다. 그 아래에는 자체 키 값을 가진 왼쪽 및 오른쪽 노드/분기가 있습니다.
오른쪽 하위 트리에는 상위 노드보다 큰 키 값이 있습니다.
왼쪽 하위 트리에는 상위 노드보다 값이 있습니다.

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

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

이진 트리 유형

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

완전한 이진 트리: 트리의 모든 레벨은 마지막 레벨의 가능한 예외로 가득 차 있습니다. 마찬가지로 모든 노드가 가득 차서 가장 왼쪽을 향합니다.
완전 이진 트리: 리프를 제외한 모든 노드에는 2개의 자식 노드가 있습니다.
균형 잡힌 또는 완벽한 이진 트리: 트리에서 모든 노드에는 두 개의 자식이 있습니다. 게다가 각 하위 노드에는 동일한 레벨이 있습니다.

전단지에 포함된 링크에 대해 더 알아보기 데이터 구조의 이진 트리 당신이 관심이 있다면.

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

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

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

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

검색: 이진 트리에서 요소를 검색합니다.
삽입: 이진 트리에 요소를 추가합니다.
삭제: 이진 트리에서 요소를 삭제합니다.

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

검색 Opera기

항상 루트 노드에서 트리 분석을 시작한 다음, 찾을 요소가 루트보다 작거나 큰지에 따라 루트 노드의 오른쪽 또는 왼쪽 하위 트리로 더 이동합니다.

검색할 요소는 10입니다.
요소를 루트 노드 12, 10 < 12와 비교하므로 왼쪽 하위 트리로 이동합니다. 오른쪽 하위 트리를 분석할 필요가 없습니다.
이제 10을 노드 7과 비교합니다. 10 > 7이므로 오른쪽 하위 트리로 이동합니다.
그런 다음 10을 다음 노드인 9, 10 > 9와 비교하고 오른쪽 하위 트리 하위를 살펴봅니다.
10은 노드의 값과 일치하고 10 = 10이며 사용자에게 값을 반환합니다.

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기

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

왼쪽에서 오른쪽 순서로 BST에 삽입해야 하는 6개의 요소 목록이 있습니다.
12를 루트 노드로 삽입하고 다음 값 7과 9를 비교하여 그에 따라 오른쪽 및 왼쪽 하위 트리에 삽입합니다.
나머지 값 19, 5, 10을 루트 노드 12와 비교하고 그에 따라 배치합니다. 19 > 12 12의 오른쪽 자식으로 배치하고, 5 < 12 & 5 < 7이므로 7의 왼쪽 자식으로 배치합니다. 이제 10을 비교하면 10은 < 12 & 10은 > 7 & 10은 > 9, 장소 10입니다. 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 – 하나의 하위 노드가 있는 노드: 노드를 삭제한 후 해당 하위 노드를 삭제된 값의 상위 노드와 연결하기만 하면 됩니다.
Case 3 두 자식이 있는 노드: 이것은 가장 어려운 상황이며 다음 두 가지 규칙에 따라 작동합니다.
3a – 선행자 순서대로: 두 개의 자식이 있는 노드를 삭제하고 삭제된 노드의 왼쪽 하위 트리에서 가장 큰 값으로 바꿔야 합니다.
3b – In Order Successor: 두 개의 자식이 있는 노드를 삭제하고 삭제된 노드의 오른쪽 하위 트리에서 가장 큰 값으로 바꿔야 합니다.

자식이 없는 노드를 삭제하는 첫 번째 삭제 사례입니다. 다이어그램에서 볼 수 있듯이 19, 10, 5에는 자녀가 없습니다. 하지만 19개는 삭제하겠습니다.
값 19를 삭제하고 노드에서 링크를 제거합니다.
19가 없는 BST의 새로운 구조 보기

이는 다이어그램에서 볼 수 있듯이 1에 9개의 자식이 있는 것처럼 XNUMX개의 자식이 있는 노드를 삭제하는 두 번째 삭제 사례입니다.
노드 9를 삭제하고 하위 노드 10으로 교체한 후 7에서 10까지의 링크를 추가합니다.
9가 없는 BST의 새로운 구조 보기

여기서는 두 개의 자식이 있는 노드 12를 삭제합니다.
노드 삭제는 순서 선행 규칙에 따라 발생합니다. 즉, 왼쪽 하위 트리 12에서 가장 큰 요소가 노드를 대체한다는 의미입니다.
노드 12를 삭제하고 왼쪽 하위 트리에서 가장 큰 값인 10으로 바꿉니다.
12를 삭제한 후 BST의 새로운 구조를 봅니다.

1 두 개의 자식이 있는 노드 12를 삭제합니다.
2 노드 삭제는 In Order Successor 규칙에 따라 발생합니다. 즉, 12의 오른쪽 하위 트리에서 가장 큰 요소가 노드를 대체합니다.
3 노드 12를 삭제하고 오른쪽 하위 트리에서 가장 큰 값인 19로 바꿉니다.
4 삭제 후 BST의 새로운 구조 보기 12

노드 삭제를 위한 의사 코드

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 to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

중요한 용어

삽입: 트리에 요소를 삽입하거나 트리를 생성합니다.
검색: 트리의 요소를 검색합니다.
선주문 순회(Preorder Traversal): 선주문 방식으로 트리를 순회합니다.
중위 순회(Inorder Traversal): 트리를 순서대로 순회합니다.
후위 순회(Postorder Traversal): 후위 방식으로 트리를 순회합니다.

제품 개요

BST는 루트 노드와 노드 값을 비교하여 다양한 연산을 수행하는 고급 수준의 알고리즘입니다.
상위-하위 계층 구조의 모든 지점은 노드를 나타냅니다. 적어도 하나의 상위 노드 또는 루트 노드가 항상 존재합니다.
왼쪽 하위 트리와 오른쪽 하위 트리가 있습니다. 왼쪽 하위 트리에는 루트 노드보다 작은 값이 포함됩니다. 그러나 오른쪽 하위 트리에는 루트 노드보다 큰 값이 포함되어 있습니다.
각 노드에는 XNUMX개, XNUMX개 또는 XNUMX개의 하위 항목이 있을 수 있습니다.
이진 검색 트리는 검색, 삽입, 삭제와 같은 기본 작업을 용이하게 해줍니다.
삭제는 가장 복잡한데, 예를 들어 자식이 없는 노드, 자식이 하나인 노드, 자식이 두 개인 노드 등 여러 가지 경우가 있습니다.
이 알고리즘은 게임, 자동 완성 데이터, 그래픽과 같은 실제 솔루션에 활용됩니다.