Учебники

Python — Дерево поиска

Декабрь 19, 2018

Бинарное дерево поиска (BST) — это дерево, в котором все узлы следуют указанным ниже свойствам. Левое поддерево узла имеет ключ, меньший или равный ключу его родительского узла. Правое поддерево узла имеет ключ больше, чем ключ его родительского узла. Таким образом, BST делит все свои поддеревья на два сегмента; левое поддерево и правое поддерево и может быть определено как — 

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

Поиск значения в B-дереве

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

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))

Когда приведенный выше код выполняется, он дает следующий результат —

92
Share: