İkili axtarış ağacı (BST, binary search tree) elə ikili ağacdır ki, hər düyün üçün: sol alt ağacın bütün açarları kiçikdir, sağ alt ağacın bütün açarları böyükdür. Bu xassə sayəsində axtarış ikili axtarış kimi işləyir: hər addımda ağacın yarısını atırıq. İkili ağacın reallaşdırılması üçün əvvəlki mövzuya baxın.

BST-də `7` açarının axtarışı: `8 → 3 → 6 → 7`
BST-də 7 açarının axtarışı: 8 → 3 → 6 → 7

Xassə və axtarış

Açar düyündən kiçikdirsə, sola, böyükdürsə, sağa gedirik; bərabərdirsə, tapdıq; None-a çatsaq, açar yoxdur. Addımların sayı ağacın hündürlüyü h ilə məhdudlaşır: O(h).

Əlavə

Axtarışla eyni yolla gedib, None yerinə yeni yarpaq qoyuruq. Yeni açar həmişə yarpaq olur; mövcud açarlar yerini dəyişmir. Dublikatları bu nümunədə rədd edirik (insert False qaytarır).

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

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

    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
            self.size = 1
            return True
        node = self.root
        while True:
            if key < node.key:
                if node.left is None:
                    node.left = Node(key)
                    break
                node = node.left
            elif key > node.key:
                if node.right is None:
                    node.right = Node(key)
                    break
                node = node.right
            else:
                return False
        self.size += 1
        return True