이진 검색 트리 시리즈 2부

구현 찾기 또는 검색.

트리에서 특정 값을 가진 노드를 찾을 때 부모 노드보다 작은 값이 있는 노드를 정렬합니다. 이는 이진 트리에 데이터를 저장할 때 특정 최적화가 수행됨을 의미합니다. 노드를 찾을 때마다 반복 후 가능한 노드 수가 절반으로 줄어듭니다. 이를 통해 솔루션을 훨씬 더 빨리 찾을 수 있습니다.

예시.

배열에 저장된 데이터에 1000,000개의 요소가 있고 배열이 정렬되어 있다고 가정합니다. 우리가 찾고 있는 노드가 1000,000n 번째 노드의 끝 근처에 있다고 가정합니다. 배열이 정렬되어 있다는 것을 알고 있기 때문에 노드를 찾는 백만 번의 비교를 하는 대신 배열의 중간 값과 값을 비교할 것입니다. , 값이 중간 값보다 크면 값이 배열의 위쪽 절반(요소 500,000-1000,000에서)에 가장 많이 존재한다는 것을 알 수 있습니다. 가능성을 고려해야 합니다. 이 핵심 통찰력을 얻음으로써 배열의 아래쪽 절반을 무시하고 대상 값과 배열의 위쪽 절반에 있는 중간 값(750,000번째 요소) 사이의 다음 비교를 수행할 수 있습니다. -1 또는 not found 를 반환하는 끝을 찾거나 평가하거나 도달할 때까지 이 작업을 반복합니다. 이 검색 방법론은 값이 존재하지 않는다는 100% 확실성이 있는 검색 데이터의 절반을 항상 제거하기 때문에 더 빠릅니다.1000,000에서 500,000...250,000...125,000,
시간 복잡도는 O(n^2) 대신 O(log n)이 됩니다. 아래를 참조하십시오.

이것이 바로 트리에서 검색이 작동하는 방식입니다.
의사 코드/따라야 할 단계:

먼저 현재 변수를 생성하고 루트 노드로 이동하여 false로 설정합니다.

현재 노드가 존재하고 발견된 변수가 여전히 false인 동안 루핑을 시작합니다.

값이 현재 노드에 저장된 값보다 작으면 current를 현재 변수의 왼쪽 속성으로 설정합니다

.

값이 전류의 값 속성보다 크면 전류를 현재 가변 권한 속성으로 설정합니다.

그렇지 않으면 찾은 변수를 true로 설정합니다.

while 외부에서 찾은 항목이 여전히 거짓인지 확인하고 거짓이면 undefined를 반환하고, 그렇지 않으면 현재 변수를 반환합니다.
JavaScript에서 코드 구현:

class Node{
    constructor(val){
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

class BST{
    constructor(){
        this.root = null;
    }
// implementation and explanation in the first part of the //series.
    insert(val){
        let newNode = new Node(val);
        if(!this.root){
            this.root = newNode;
        }else{
            let current = this.root;
            while(true){
                if(val < current.val){
                    if(current.left === null){
                        current.left = newNode;
                        return this
                    }else{
                        current = current.left;
                    }
                }else{
                    if(current.right === null){
                        current.right = newNode;
                        return this
                    }else{
                        current = current.right
                    }
                }
            }

        }

    }
    find(val){
        let current  = this.root;
        let found = false;
        while(current && !found){
            if(val < current.val){
                 current = current.left;
                }
            }else if(val > current.val){
                current = current.right;
                }else{
              found = true
            }
        }
        if(!found) return undefined
        return current
    }


    }

파이썬에서:-

class Node:
    def __init__(self,val):
        self.val = val
        self.left = None
        self.right = None


class BST:
    def __init__(self):
        self.root= None

    def insert(self, val):
         newNode = Node(val)
         if self.root == None:
             self.root= newNode
         else:
             current = self.root
             while True:
                 if val< current.val:
                     if current.left == None:
                         current.left = newNode
                         return self
                     else:
                         current= current.left 
                 else:
                     if(current.right == None):
                         current.right = newNode
                         return self
                     else:
                         current = current.right

    def  find(self, val):          
                current= self.root
                found = False
                while current and not found:
                    if val < current.val:
                        current = current.left
                    elif val > current.val:
                        current= current.right
                    else:
                        found = True
                if(not found): return "not found"
                return current



bst = BST()
bst.insert(100)
bst.insert(200)
bst.insert(150)
bst.insert(175)
bst.insert(160)
bst.insert(180)
bst.insert(75)
bst.insert(50)
bst.insert(65)
bst.insert(40)
bst.insert(55)
bst.insert(20)

print(bst.find(21))

다음 시리즈에서는 검색 방법론에 대해 살펴보겠습니다. 너비 우선 검색으로 시작합니다.