Python-검색 트리

이진 검색 트리 (BST)는 모든 노드가 아래에 언급 된 속성을 따르는 트리입니다. 노드의 왼쪽 하위 트리에는 부모 노드의 키보다 작거나 같은 키가 있습니다. 노드의 오른쪽 하위 트리에는 상위 노드의 키보다 큰 키가 있습니다. 따라서 BST는 모든 하위 트리를 두 개의 세그먼트로 나눕니다. 왼쪽 하위 트리와 오른쪽 하위 트리는 다음과 같이 정의 할 수 있습니다.

left_subtree (keys)  ≤  node (key)  ≤  right_subtree (keys)

B- 트리에서 값 검색

트리에서 값을 검색하려면 들어오는 값을 나가는 노드 값과 비교해야합니다. 여기에서도 노드를 왼쪽에서 오른쪽으로 이동 한 다음 마지막으로 부모와 함께 이동합니다. 검색된 값이 exitign 값과 일치하지 않으면 찾을 수 없음 메시지를 반환하고 그렇지 않으면 찾은 메시지를 반환합니다.

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data

# Insert method to create nodes
    def insert(self, data):

        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data
# findval method to compare the value with nodes
    def findval(self, lkpval):
        if lkpval < self.data:
            if self.left is None:
                return str(lkpval)+" Not Found"
            return self.left.findval(lkpval)
        elif lkpval > self.data:
            if self.right is None:
                return str(lkpval)+" Not Found"
            return self.right.findval(lkpval)
        else:
            print(str(self.data) + ' is found')
# Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()


root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
print(root.findval(7))
print(root.findval(14))

위의 코드가 실행되면 다음과 같은 결과가 생성됩니다.

7 Not Found
14 is found