Реализация двоичного дерева поиска в Python: подробное руководство - Fcodenotes

Двоичные деревья поиска (BST) — это фундаментальные структуры данных в информатике. В этой статье мы рассмотрим реализацию двоичного дерева поиска в Python. Мы рассмотрим различные методы и предоставим примеры кода, которые помогут вам понять и эффективно реализовать BST.

Содержание:

Обзор двоичных деревьев поиска
Реализация класса узла
Операция вставки
В поисках ключа
Операция удаления
Методы обхода дерева
а. Обход по порядку
b. Обход предзаказа
c. Обход постзаказа
Нахождение минимального и максимального элементов
Высота дерева
Проверка того, является ли дерево двоичным деревом поиска
Балансировка двоичного дерева поиска
Вывод
Обзор двоичных деревьев поиска.
Двоичное дерево поиска — это двоичное дерево, в котором каждый узел имеет ключ/значение и удовлетворяет следующему свойству: ключ в любом узле больше, чем все ключи в его левой части. поддерево и меньше всех ключей в его правом поддереве.

Реализация класса узла:

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

Операция вставки:

def insert(root, key):
if root is None:
    return Node(key)
if key < root.key:
    root.left = insert(root.left, key)
else:
    root.right = insert(root.right, key)
return root

Поиск ключа:

def search(root, key):
if root is None or root.key == key:
    return root
if key < root.key:
    return search(root.left, key)
return search(root.right, key)

Операция удаления:

def delete(root, key):
if root is None:
    return root
if key < root.key:
    root.left = delete(root.left, key)
elif key > root.key:
    root.right = delete(root.right, key)
else:
    if root.left is None:
        return root.right
    elif root.right is None:
        return root.left
    root.key = minValue(root.right)
    root.right = delete(root.right, root.key)
return root

Методы обхода дерева:
а. Обход по порядку:

def inorder(root):
if root:
    inorder(root.left)
    print(root.key)
    inorder(root.right)

б. Обход предзаказа:

def preorder(root):
    if root:
        print(root.key)
        preorder(root.left)
        preorder(root.right)

в. Обход постзаказа:

def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.key)

Нахождение минимального и максимального элементов:

def minValue(root):
current = root
while current.left is not None:
    current = current.left
return current.key
def maxValue(root):
current = root
while current.right is not None:
    current = current.right
return current.key

Высота дерева:

def height(root):
if root is None:
    return 0
return 1 + max(height(root.left), height(root.right))

Проверка того, является ли дерево двоичным деревом поиска:

def isBinarySearchTree(root):
return isBSTUtil(root, float('-inf'), float('inf'))
def isBSTUtil(root, min_value, max_value):
if root is None:
    return True
if root.key < min_value or root.key > max_value:
    return False
return (isBSTUtil(root.left, min_value, root.key - 1) and
        isBSTUtil(root.right, root.key + 1, max_value))

Балансировка двоичного дерева поиска.
Существуют различные алгоритмы балансировки BST, например дерево AVL или красно-черное дерево. Реализация этих алгоритмов выходит за рамки этой статьи, но их можно изучить отдельно.
В этой статье мы рассмотрели реализацию двоичного дерева поиска в Python. Мы рассмотрели различные методы, включая вставку, удаление, поиск, обход дерева, поиск минимальных и максимальных элементов, проверку того, является ли дерево бинарным деревом поиска, и вычисление высоты дерева. Понимание и реализация этих методов позволит вам эффективно работать с двоичными деревьями поиска в Python.