데이터 구조: Go가 있는 두 갈래 검색 트리

이 감동적인 탐색을 계속하고 데이터 구조와 알고리즘에 대한 지식을 더 많이 배워라.나는 링크 목록에서 마지막으로 토론한 지식을 바탕으로 하는 두 갈래 검색 트리에 대해 이야기하고 싶다. 링크 목록은 본문book을 인용하면 이 글을 찾을 수 있다.

이진 검색 트리를 선택한 이유는 무엇입니까?

일부 데이터 구조는 빠른 검색이나 유연한 업데이트를 허용하지만 둘 다 가질 수는 없다.정렬되지 않은 이중 체인 테이블은 일정한 시간 내에 삽입 O(1) 을 지원하지만, 최악의 경우 선형 시간 O(n) 이 필요합니다.정렬 수조는 2진 검색을 지원하는데, 이것은 대수 시간O(logn) 내에서 검색하는 데 도움이 되지만, 그 대가는 선형 시간 업데이트이다.
두 갈래 검색 트리는 대수 시간O(logn) 내에 빠른 검색과 업데이트를 할 수 있지만, 경고가 있습니다. 두 갈래 검색 트리의 균형을 논의할 때 이에 대해 설명할 것입니다.
트리의 배열과 균형은 왼쪽 트리의 노드 키가 오른쪽 트리의 키보다 작은 방식으로 이루어져 트리가 항상 정렬됩니다.

두 갈래 검색 트리의 실현

두 갈래 검색 트리를 만들기 위해서는 노드당 2개의 바늘이 있는 체인 테이블이 필요합니다.
그 사상은 왼쪽 나무와 오른쪽 나무가 있는데 노드는 키로 표시한다.나는 두 갈래 검색 트리에서 검색, 반복, 삽입을 실현할 것이다.
나무의 노드는 하나이다.왼쪽 포인터 2.오른쪽 포인터부모 포인터 4(옵션)삽입된 값을 저장하는 데이터 필드입니다.이 구현된 모든 코드와 테스트는 github 에서 찾을 수 있습니다.
이원 검색 트리를 만들려면 root가 필요합니다. 그 중 모든 내용이 비어 있을 수도 있고 노드와 좌우 트리라고 불리는 이원 검색 트리로 구성될 수도 있습니다. 좌우 트리는 노드로 구성되고 하나의 노드(트리)는 이원 검색 트리의 최소 단원과 기초입니다. 아래와 같습니다.

    // Tree is the basic structure or node in a binary search tree.
    type Tree struct {
        parent *Tree  // parent can be nil i.e Root tree
        left   *Tree  // left child or left subtree
        right  *Tree  // right child or right subtree
        Item   string // data held by the node
    }

아버지나무는 한 그루의 나무가 될 수 있지만, 뿌리나무가 있는 경우, 그것은 비어 있을 것이며, 왼쪽과 오른쪽도 비어 있을 것이다. 이것은 우리가 나무의 끝에 있다는 것을 나타낸다.우리는 이 데이터 구조를 사용하여 사전 (승승 순서에 따라 정렬된 단어 집합) 을 모델링할 것이다.

    // BinarySearchTree to store the words of a dictionary.
    type BinarySearchTree struct {
        Root *Tree
    }

삽입

나는 두 가지 다른 삽입 조작 실현, 귀속과 비귀속 방법이 있다.

비귀속
이런 방법은 코드가 더 많고 추리하기 쉽다.우리는 뿌리부터 두 갈래 검색 트리를 훑어보고 삽입할 항목에 따라 다음과 같은 결정점을 가지고 귀속 방법의 배후 개념을 형성할 것이다.

루트가 비어 있으면 이 항목을 삽입하여 부모 트리, 왼쪽 트리 및 오른쪽 트리 또는 하위 트리가 0인 새 트리를 생성합니다.

만약 삽입할 항목이 노드의 현재 항목보다 작다면, 우리는 왼쪽 트리로 이동하여 왼쪽 트리의 끝, 즉 0에 도달할 때까지 계속 검색하고, 거기에 새 항목을 삽입하여 새 트리로 봉인합니다.

삽입할 항목이 노드의 현재 항목보다 크면 위의 절차를 반복하지만 왼쪽 트리가 아니라 오른쪽 트리로 이동합니다.

다음과 같습니다.

    func (bt *BinarySearchTree) NormalInsert(item string) {
        if bt.Root == nil {
            bt.Root = &Tree{
                Item: item,
            }
            return
        }
        currentTree := bt.Root

    insertionLoop:
        for {
            switch {
            // go to the left subtree
            case item < currentTree.Item:
                if currentTree.left == nil { // at the end of the left subtrees
                    // attach the new node
                    currentTree.left = &Tree{
                        Item:   item,
                        parent: currentTree,
                    }
                    break insertionLoop
                } else {
                    currentTree = currentTree.left
                }
                break
            // go to the right subtree
            case item > currentTree.Item:
                if currentTree.right == nil { // at the end of the right subtree
                    // attach the new node
                    currentTree.right = &Tree{
                        Item:   item,
                        parent: currentTree,
                    }
                    break insertionLoop
                } else {
                    currentTree = currentTree.right
                }
                break
            default:
                break insertionLoop
            }
        }
    }

우리는 순환에 라벨을 붙여야 한다. 왜냐하면 우리가 break switch 문장에 있을 때, 그것은 순환이 아니라 스위치에서 벗어났기 때문이다.

차례로 돌아가다
위에서 언급한 바와 같이, 이 방법은 코드가 더 적지만, 특히 새 트리를 아버지 트리에 추가하려면 위와 같은 방법을 따라야 한다.

    func (bt *BinarySearchTree) RecursiveInsert(currentTree **Tree, item string, parent *Tree) {
        // currentTree is a pointer to the memory location(also a pointer) where the current node tree
        // is stored. This is needed because, when we get to a tree that is empty and we need to insert
        // the new item, we'll need to replace the empty space (which is to hold a tree) with the new tree, this warrants having access to the location.
        // If you don't do this, your update will be detached from the main binary search tree.

        // when we have come to the end of the search.
        if *currentTree == nil {
            newTree := &Tree{
                Item:   item,
                left:   nil,
                right:  nil,
                parent: parent,
            }
            // Attach to its parent, by getting the memory location where the currentTree.
            *currentTree = newTree
            return
        }

        // Recursively search for where to put the item.
        if item < (*currentTree).Item { // diverge to the left subtree
            bt.RecursiveInsert(&(*currentTree).left, item, *currentTree)
        } else {
            bt.RecursiveInsert(&(*currentTree).right, item, *currentTree)
        }
    }

새 노드를 트리에 연결하는 데는 일정한 시간이 필요하지만, 노드를 연결하기 전에 실행하는 검색 작업에 사용되는 운행 시간은 O(h), h-트리의 높이
주의, 이곳의 삽입은 균형이 잡힌 검색 트리를 보장할 수 없습니다. 제가 붉은색 트리와 Slay 트리를 토론할 때 이것은 다른 글에서 붉은색 트리와 Slay 트리의 높이를 O(logn)로 보증합니다. 삽입, 업데이트와 삭제에 적용되고 트리가 변이에 응답하여 균형에 가깝게 함으로써 트리의 높이를 시종 또는 가깝게 할 수 있습니다O(log n).
지금까지 우리가 얻은 것은 무작위 두 갈래 검색 트리였는데, 그것도 매우 좋았지만, 만약 남쪽으로 삽입된다면 (사용자가 삽입한 값이나 항목을 제어할 수 없음) 우리는 최종적으로 나무의 O(n) 높이를 얻을 수 있다.

검색
두 갈래 검색 트리를 표시하는 것은 매우 중요하다. 이렇게 하면 우리는 그 표지부호를 사용하여 모든 나무를 유일하게 표시할 수 있다.
다음은 이 작업을 수행할 때 고려해야 할 단계입니다.

나무의 뿌리부터 검색

검색할 키가 있으면

키가 루트의 키나 식별자보다 크거나 작은지 확인하면 우리가 나무의 왼쪽 자급인지 오른쪽 자급인지를 확인할 수 있습니다.

항목을 찾거나 트리의 끝에 도달할 때까지 이 절차를 반복적으로 계속합니다

검색 알고리즘은 O(h) 시간 내에 실행되며, 그 중에서 h는 두 갈래 검색 트리의 높이이다
트리의 최소 노드를 찾으려면 이해해야 한다. 가장 왼쪽의 트리는 가장 작은 항목을 가지고 있고, 가장 큰 값에 대해 가장 오른쪽의 트리는 트리 중에서 가장 높은 항목을 가지고 있다.가장 작은 키는 루트의 왼쪽 트리에 있어야 합니다. 왜냐하면 왼쪽 트리의 모든 키는 루트의 값보다 작고, 가장 큰 키는 오른쪽 트리에 있습니다. 왜냐하면 오른쪽 트리의 키는 루트보다 높기 때문입니다.이러한 작업은 다음과 같습니다.
검색:

    // Search searches for an item, it expects to start from the Root.
    func (bt *BinarySearchTree) Search(item string) string {

        if result := bt.Root.Search(bt.Root, item); result != nil { // found!
            return result.Item
        }
        return ""
    }

최소값:

    func (bt *BinarySearchTree) FindMinimum() *Tree {
        // start from the Root and move to the left subtrees
        minTree := bt.Root

        for minTree.left != nil {
            minTree = minTree.left
        }
        return minTree
    }

최대값:

    // FindMaximum returns the largest or highest item item in the tree.
    func (bt *BinarySearchTree) FindMaximum() *Tree {
        // start from the Root and move right wards
        maxTree := bt.Root

        for maxTree.right != nil {
            maxTree = maxTree.right
        }
        return maxTree
    }

두루 다니다

이것은 루트 트리의 모든 노드에 접근하는 데 관한 것으로, 이것은 많은 알고리즘에서 매우 중요한 부분이다.이것도 그림 속의 노드와 가장자리를 두루 훑어보는 기초이다.
가장 작은 키는 뿌리의 왼쪽에, 가장 큰 키는 뿌리 나무의 오른쪽에 있기 때문에 두 갈래 검색 트리의 요소는 이미 정렬되었다.
이것은 귀속 방법을 사용하여 트리의 노드에 접근하고 왼쪽 트리를 처리하며 이 트리의 항목을 처리하고 귀속 액세스 오른쪽 트리를 통해 이루어진다.이 작업의 완료 순서는 1입니다.차례대로사전 정렬 반복 3.뒤돌아 다니다

순서대로 훑어보기:
왼쪽 트리, 처리 항목, 오른쪽 트리를 두루 훑어보십시오. 귀속된 색인은 우리가 하위 트리가 없는 잎이나 노드에 도착했을 때, 즉 왼쪽 트리와 오른쪽 트리가 0입니다.

사전 정렬 반복:
먼저 트리의 항목을 처리한 다음 왼쪽 트리와 오른쪽 트리를 두루 돌아봅니다

다음 순서를 반복합니다.
먼저 왼쪽 나무를 훑어본 다음에 오른쪽 나무를 훑어본 다음에 나무의 항목을 처리한다.
2진 검색 트리가 연산 순서가 매우 중요한 산술 표현식이나 논리 표현식을 표시할 때 앞뒤와 뒤의 순서를 반복하는 것이 매우 편리하다.
반복된 운행 시간은 선형적O(n)이며, 항목마다 한 번만 방문하기 때문이다.
다음은 순서가 반복되는 예입니다. github 에서 미리 순서와 다음 순서를 얻을 수 있습니다.
순서대로 훑어보기:

    // InOrderTraversal traverse in the order [smallest ... largest] [allLeft ... allRight]
    func (bt *BinarySearchTree) InOrderTraversal(t *Tree, processItem func (string)) {
        if t != nil {
            bt.InOrderTraversal(t.left, processItem)
            // process the item in the tree using the power of closure
            processItem(t.Item)
            bt.InOrderTraversal(t.right, processItem)
        }
}

마지막 생각

Picking the wrong data structure for the job can be disastrous in terms of performance. Identifying the very best data structure is usually not as critical because there can be several choices that perform similarly. - Steven S. Skiena

해결하려는 문제는 사용자가 사용하는 데이터 구조 유형을 항상 알려야 합니다.예전과 같이, 이것은 학습 여행입니다. 만약 당신이 문제나 피드백이 있다면, 나는 당신의 편지를 듣고 매우 기쁩니다. 즐겁게 놀기를 바랍니다.