Python에서 이진 검색 트리를 구현하는 방법은 무엇입니까?

트리 소개

트리는 연결 리스트나 해시 테이블과 다릅니다. 트리는 이진 트리, 이진 검색 트리, B-트리, B+ 트리, 레드-블랙 트리로 구분됩니다. , 등.

트리는 n개의 제한된 노드로 구성된 계층적 관계의 집합인 데이터 구조입니다. 이를 그림으로 표현해 보면 마치 거꾸로 된 나무처럼 보이는 것을 알 수 있습니다. 따라서 우리는 이러한 유형의 데이터 구조를 루트가 맨 위에 있고 잎이 맨 아래에 있는 트리라고 통칭합니다. 일반 트리에는 다음과 같은 특성이 있습니다.

• 각 노드에는 0개 이상의 하위 노드가 있습니다.

• 상위 노드가 없는 노드를 루트 노드라고 합니다.

• 루트가 아닌 각 노드에는 상위 노드가 하나만 있고 하나만 있습니다. 노드

• 각 하위 노드는 여러 개의 분리된 하위 트리로 나눌 수 있습니다.

이진 트리의 정의는 다음과 같습니다. 각 노드에는 최대 2개의 하위 노드가 있습니다. 즉, 각 노드에는 다음 네 가지 상황만 있을 수 있습니다.

• 왼쪽 하위 트리와 오른쪽 하위 트리가 모두 비어 있음

• 왼쪽 하위 트리만 존재함

• 오른쪽 하위 트리만 존재함

• The 왼쪽 하위 트리 트리와 오른쪽 하위 트리가 모두 존재합니다

이진 검색 트리

이진 검색 트리는 이진 정렬 트리라고도 하며 다음과 같은 속성을 갖는 이진 트리입니다.

• 의 왼쪽 하위 트리가 비어 있지 않으면 왼쪽 하위 트리에 있는 모든 노드의 값이 루트 노드의 값보다 작습니다. 오른쪽 하위 트리가 비어 있지 않으면 오른쪽 하위 트리에 있는 모든 노드의 값이 루트 노드의 값보다 작습니다. 루트 노드의 값보다 큽니다

• 왼쪽과 오른쪽 하위 트리도 각각 이진 검색 트리입니다.

Python의 몇 가지 일반적인 구현 방법을 나열합니다.

1 클래스와 재귀 함수를 사용하여 구현합니다. 노드 값, 왼쪽 및 오른쪽 하위 노드 및 기타 속성을 포함한 노드 클래스를 정의한 다음 재귀 함수를 통해 삽입, 검색, 삭제 및 기타 작업을 구현합니다. 코드 예시는 다음과 같습니다.

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

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

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert(value, self.root)

    def _insert(self, value, node):
        if value < node.data:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert(value, node.left)
        elif value > node.data:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert(value, node.right)

    def search(self, value):
        if self.root is None:
            return False
        else:
            return self._search(value, self.root)

    def _search(self, value, node):
        if node is None:
            return False
        elif node.data == value:
            return True
        elif value < node.data:
            return self._search(value, node.left)
        else:
            return self._search(value, node.right)

    def delete(self, value):
        if self.root is None:
            return False
        else:
            self.root = self._delete(value, self.root)

    def _delete(self, value, node):
        if node is None:
            return node
        elif value < node.data:
            node.left = self._delete(value, node.left)
        elif value > node.data:
            node.right = self._delete(value, node.right)
        else:
            if node.left is None and node.right is None:
                del node
                return None
            elif node.left is None:
                temp = node.right
                del node
                return temp
            elif node.right is None:
                temp = node.left
                del node
                return temp
            else:
                temp = self._find_min(node.right)
                node.data = temp.data
                node.right = self._delete(temp.data, node.right)
        return node

    def _find_min(self, node):
        while node.left is not None:
            node = node.left
        return node

2. 목록 구현 사용

목록을 사용하여 이진 검색 트리의 요소를 저장한 후 요소의 위치 관계를 통해 삽입, 검색, 삭제 등의 작업을 구현합니다. 목록에 있습니다. 코드 예시는 다음과 같습니다.

class BST:
    def __init__(self):
        self.values = []

    def insert(self, value):
        if len(self.values) == 0:
            self.values.append(value)
        else:
            self._insert(value, 0)

    def _insert(self, value, index):
        if value < self.values[index]:
            left_child_index = 2 * index + 1
            if left_child_index >= len(self.values):
                self.values.extend([None] * (left_child_index - len(self.values) + 1))
            if self.values[left_child_index] is None:
                self.values[left_child_index] = value
            else:
                self._insert(value, left_child_index)
        else:
            right_child_index = 2 * index + 2
            if right_child_index >= len(self.values):
                self.values.extend([None] * (right_child_index - len(self.values) + 1))
            if self.values[right_child_index] is None:
                self.values[right_child_index] = value
            else:
                self._insert(value, right_child_index)

    def search(self, value):
        if value in self.values:
            return True
        else:
            return False

    def delete(self, value):
        if value not in self.values:
            return False
        else:
            index = self.values.index(value)
            self._delete(index)
            return True

    def _delete(self, index):
        left_child_index = 2 * index + 1
        right_child_index = 2 * index + 2
        if left_child_index < len(self.values) and self.values[left_child_index] is not None:
            self._delete(left_child_index)
        if right_child_index < len(self.values) and self.values[right_child_index] is not None:
            self

3. 사전을 사용하여

구현합니다. 여기서 사전의 키는 노드 값을 나타내고, 사전의 값은 왼쪽 및 오른쪽 하위 노드를 포함하는 사전입니다. 코드 예시는 다음과 같습니다.

def insert(tree, value):
    if not tree:
        return {value: {}}
    elif value < list(tree.keys())[0]:
        tree[list(tree.keys())[0]] = insert(tree[list(tree.keys())[0]], value)
    else:
        tree[list(tree.keys())[0]][value] = {}
    return tree

def search(tree, value):
    if not tree:
        return False
    elif list(tree.keys())[0] == value:
        return True
    elif value < list(tree.keys())[0]:
        return search(tree[list(tree.keys())[0]], value)
    else:
        return search(tree[list(tree.keys())[0]].get(value), value)

def delete(tree, value):
    if not search(tree, value):
        return False
    else:
        if list(tree.keys())[0] == value:
            if not tree[list(tree.keys())[0]]:
                del tree[list(tree.keys())[0]]
            elif len(tree[list(tree.keys())[0]]) == 1:
                tree[list(tree.keys())[0]] = list(tree[list(tree.keys())[0]].values())[0]
            else:
                min_key = min(list(tree[list(tree.keys())[0]+1].keys()))
                tree[min_key] = tree[list(tree.keys())[0]+1][min_key]
                tree[min_key][list(tree.keys())[0]] = tree[list(tree.keys())[0]]
                del tree[list(tree.keys())[0]]
        elif value < list(tree.keys())[0]:
            tree[list(tree.keys())[0]] = delete(tree[list(tree.keys())[0]], value)
        else:
            tree[list(tree.keys())[0]][value] = delete(tree[list(tree.keys())[0]].get(value), value)
    return tree

사전이 순서가 지정되지 않았기 때문에 이 구현으로 인해 이진 검색 트리가 불균형하게 되어 삽입, 검색 및 삭제 작업의 효율성에 영향을 줄 수 있습니다.

4. 스택을 사용하여 구현

스택(Stack)을 사용하면 반복을 통해 삽입, 검색, 삭제 및 기타 작업을 구현할 수 있는 간단한 이진 검색 트리를 구현할 수 있습니다. 구체적인 구현 프로세스는 다음과 같습니다.

노드 값, 왼쪽 및 오른쪽 하위 노드 및 기타 속성을 포함하여 노드 클래스를 정의합니다.
스택을 정의하고 처음에는 루트 노드를 스택에 푸시합니다.
스택이 비어 있지 않으면 스택의 최상위 요소를 꺼내서 연산합니다. 삽입할 값이 현재 노드 값보다 작으면 삽입할 값을 왼쪽 자식 노드로 삽입하고 왼쪽 자식 노드를 스택에 푸시합니다. 삽입할 값이 현재 노드 값보다 크면 삽입할 값을 오른쪽 자식 노드로 삽입하고 값을 찾으면 오른쪽 자식 노드를 스택에 푸시합니다. 또는 삭제된 값이 현재 노드 값과 같으면 노드를 반환하거나 삭제합니다.
작업이 완료된 후 계속해서 스택에서 다음 노드를 가져와 스택이 빌 때까지 작업합니다.
이 구현에서는 트리 순회 프로세스를 저장하기 위해 스택을 사용하기 때문에 메모리 사용량이 높아질 수 있다는 점에 유의해야 합니다. 또한 스택의 특성상 이 구현은 깊이 우선 탐색(DFS)만 지원하고 너비 우선 탐색(BFS)은 지원하지 않습니다.

다음은 의사 코드의 예입니다.

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

def insert(root, value):
    if not root:
        return Node(value)
    stack = [root]
    while stack:
        node = stack.pop()
        if value < node.data:
            if node.left is None:
                node.left = Node(value)
                break
            else:
                stack.append(node.left)
        elif value > node.data:
            if node.right is None:
                node.right = Node(value)
                break
            else:
                stack.append(node.right)

def search(root, value):
    stack = [root]
    while stack:
        node = stack.pop()
        if node.data == value:
            return True
        elif value < node.data and node.left:
            stack.append(node.left)
        elif value > node.data and node.right:
            stack.append(node.right)
    return False

def delete(root, value):
    if root is None:
        return None
    if value < root.data:
        root.left = delete(root.left, value)
    elif value > root.data:
        root.right = delete(root.right, value)
    else:
        if root.left is None:
            temp = root.right
            del root
            return temp
        elif root.right is None:
            temp = root.left
            del root
            return temp
        else:
            temp = root.right
            while temp.left is not None:
                temp = temp.left
            root.data = temp.data
            root.right = delete(root.right, temp.data)
    return root

위 내용은 Python에서 이진 검색 트리를 구현하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!