How to implement binary search tree algorithm in python

Introduction to binary search tree algorithm

Binary Search Tree (BST) is a common data structure that supports a series of dynamic collection operations, including search, insertion, deletion and traversal.

In a binary search tree, for each node X in the tree, all items in its left subtree have less values than items in X, and all items in its right subtree have greater values than items in X.

1. Properties of binary search tree

Unique root node: The non-empty binary search tree has a root node.
Left subtree: For each node X in the tree, all items in its left subtree have less values than those in X.
Right subtree: For each node X in the tree, all items in its right subtree have greater values than those in X.
In-order traversal: Perform in-order traversal (left-root-right) on the binary search tree to obtain a sequence of node values arranged in ascending order.

2. Basic Operation

insert

Start at the root node.
If the value you want to insert is smaller than the value of the current node, move to the left subtree.
If the value you want to insert is greater than the value of the current node, move to the right subtree.
Repeat steps 2 and 3 until an empty location is found to insert a new node.

search

Start at the root node.
If the value you are searching for is less than the value of the current node, move to the left subtree.
If the value you are searching for is greater than the value of the current node, move to the right subtree.
Repeat steps 2 and 3 until the values are found equal or reach the leaf node (no child node).

delete

The deletion operation is a little more complicated because it requires handling three situations:

The node to be deleted is a leaf node: directly delete the node and modify the link to its parent node.
The node to be deleted has a child: replace the node with its child node and modify the link to its parent node.
The node to be deleted has two child nodes: find the smallest node in the right subtree of that node (or the largest node in the left subtree), replace the value of the node with the value of that node, and delete the smallest node in the right subtree (or the largest node in the left subtree).

3. Sample code (Python)

Here is just a very basic sample code for insertion and search:

class TreeNode:
    def __init__(self, key):
         = None
         = None
         = key

class BinarySearchTree:
    def __init__(self):
         = None

    def insert(self, key):
        if  is None:
             = TreeNode(key)
        else:
            self._insert_rec(, key)

    def _insert_rec(self, root, key):
        if key &lt; :
            if  is None:
                 = TreeNode(key)
            else:
                self._insert_rec(, key)
        elif key &gt; :
            if  is None:
                 = TreeNode(key)
            else:
                self._insert_rec(, key)

    def search(self, key):
        return self._search_rec(, key)

    def _search_rec(self, root, key):
        if root is None or  == key:
            return root is not None
        if key &lt; :
            return self._search_rec(, key)
        return self._search_rec(, key)

#User Examplebst = BinarySearchTree()
(50)
(30)
(20)
(40)
(70)
(60)
(80)

print((40))  # Output: Trueprint((25))  # Output: False

Please note:

This sample code only implements the insertion and search functions, and does not implement the delete operation.
The deletion operation requires more logic to handle different situations.

Example of binary search tree algorithm python implementation

Here is a simple Python algorithm to implement binary search tree:

# Define the node of the binary search treeclass Node:
    def __init__(self, value):
         = value
         = None
         = None

# Define binary search treeclass BinarySearchTree:
    def __init__(self):
         = None

    # Insert node    def insert(self, value):
        if  is None:
             = Node(value)
        else:
            self._insert_recursive(, value)

    def _insert_recursive(self, node, value):
        if value &lt; :
            if  is None:
                 = Node(value)
            else:
                self._insert_recursive(, value)
        else:
            if  is None:
                 = Node(value)
            else:
                self._insert_recursive(, value)

    # Find nodes    def find(self, value):
        return self._find_recursive(, value)

    def _find_recursive(self, node, value):
        if node is None or  == value:
            return node
        if value &lt; :
            return self._find_recursive(, value)
        return self._find_recursive(, value)

    # Delete nodes    def delete(self, value):
         = self._delete_recursive(, value)

    def _delete_recursive(self, node, value):
        if node is None:
            return node
        if value &lt; :
             = self._delete_recursive(, value)
        elif value &gt; :
             = self._delete_recursive(, value)
        else:
            # Find the node you want to delete            if  is None:
                return 
            elif  is None:
                return 
            else:
                # Find the smallest node in the right subtree and replace the current node                min_node = self._find_min()
                 = min_node.value
                 = self._delete_recursive(, min_node.value)
        return node

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

    # In-order traversal    def inorder_traversal(self):
        self._inorder_traversal_recursive()

    def _inorder_traversal_recursive(self, node):
        if node is not None:
            self._inorder_traversal_recursive()
            print(, end=" ")
            self._inorder_traversal_recursive()

How to use:

bst = BinarySearchTree()
(8)
(3)
(10)
(1)
(6)
(14)
(4)
(7)
(13)

bst.inorder_traversal()  # Output: 1 3 4 6 7 8 10 13 14
(8)
bst.inorder_traversal()  # Output: 1 3 4 6 7 10 13 14
node = (6)
print()  # Output：6

This is a basic binary search tree algorithm implementation, including insertion, search, deletion and in-order traversal operations. You can further expand and optimize this implementation as needed.

Summarize

The above is personal experience. I hope you can give you a reference and I hope you can support me more.