Бинарные деревья поиска.

Определения

Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет значение (оно же является в данном случае и ключом) и ссылки на левого и правого потомка. Узел, находящийся на самом верхнем уровне (не являющийся чьим либо потомком) называется корнем. Узлы, не имеющие потомков (оба потомка которых равны NULL) называются листьями.

Бинарное дерево поиска — это бинарное дерево, обладающее дополнительными свойствами: значение левого потомка меньше значения родителя, а значение правого потомка больше значения родителя для каждого узла дерева. То есть, данные в бинарном дереве поиска хранятся в отсортированном виде. При каждой операции вставки нового или удаления существующего узла отсортированный порядок дерева сохраняется. При поиске элемента сравнивается искомое значение с корнем. Если искомое больше корня, то поиск продолжается в правом потомке корня, если меньше, то в левом, если равно, то значение найдено и поиск прекращается.

Сбалансированное бинарное дерево поиска — это бинарное дерево поиска с логарифмической высотой. Данное определение скорее идейное, чем строгое. Строгое определение оперирует разницей глубины самого глубокого и самого неглубокого листа (в AVL-деревьях) или отношением глубины самого глубокого и самого неглубокого листа (в красно-черных деревьях). В сбалансированном бинарном дереве поиска операции поиска, вставки и удаления выполняются за логарифмическое время (так как путь к любому листу от корня не более логарифма). В вырожденном случае несбалансированного бинарного дерева поиска, например, когда в пустое дерево вставлялась отсортированная последовательность, дерево превратится в линейный список, и операции поиска, вставки и удаления будут выполняться за линейное время. Поэтому балансировка дерева крайне важна. Технически балансировка осуществляется поворотами частей дерева при вставке нового элемента, если вставка данного элемента нарушила условие сбалансированности.

class Node:  
    def __init__(self, key):  
        self.left = None  
        self.right = None  
        self.val = key  
  
class BinarySearchTree:  
    def __init__(self):  
        self.root = None  
	  
    def insert(self, root, key):  
        if root is None:  
            return Node(key)  
	  
        if root.val < key:  
            root.right = self.insert(root.right, key)  
        else:  
            root.left = self.insert(root.left, key)  
	  
        return root  
	  
    def inorderTraversal(self, root):  
        if root:  
            self.inorderTraversal(root.left)  
            print(root.val)  
            self.inorderTraversal(root.right)  
	  
    def addKey(self, key):  
        self.root = self.insert(self.root, key)  
	  
    def search(self, root, key):  
        if root is None or root.val == key:  
            return root  
        if root.val < key:  
            return self.search(root.right, key)  
        return self.search(root.left, key)  
	  
    def delete(self, root, key):  
        if root is None:  
            return root  
        if key < root.val:  
            root.left = self.delete(root.left, key)  
        elif key > root.val:  
            root.right = self.delete(root.right, key)  
        else:  
            if root.left is None:  
                temp = root.right  
                root = None  
                return temp  
            elif root.right is None:  
                temp = root.left  
                root = None  
                return temp  
            temp = self.minValueNode(root.right)  
            root.key = temp.key  
            root.right = self.delete(root.right, temp.key)  
        return root  
	  
    def minValueNode(self, root):  
        current = root  
        while current.left is not None:  
            current = current.left  
        return current  
	  
    def maxValue(self):  
        current = self.root  
        while current.right:  
            current = current.right  
        return current.val  
	  
    def minValue(self):  
        current = self.root  
        while current.left:  
            current = current.left  
        return current.val

1. Вставка элемента:

   • Начинаем с корневого узла.
   • Если дерево пусто, новый узел становится корнем.
   • В противном случае сравниваем значение нового узла с корневым узлом и рекурсивно вставляем его в левое или правое поддерево.

2. Поиск элемента:

   • Начинаем с корневого узла.
   • Сравниваем искомое значение с текущим узлом.
   • Если значение меньше, переходим к левому поддереву, если больше — к правому.
   • Если значение равно, элемент найден.
   • Повторяем процесс рекурсивно или итеративно.

3. Удаление элемента:

   • Найти узел, который нужно удалить.
   • Если узел не имеет потомков (лист), просто удаляем его.
   • Если узел имеет одного потомка, заменяем его этим потомком.
   • Если узел имеет двух потомков, находим наименьший узел в правом поддереве (или наибольший в левом), заменяем его значением удаляемого узла и удаляем этот наименьший узел.