What are the methods to implement binary search tree in python

Introduction to trees

Trees are different from linked lists or hash tables. They are a non-linear data structure. Trees are divided into binary trees, binary search trees, B-trees, B-trees, red-black trees, etc. .

Tree is a data structure, which is a collection of hierarchical relationships composed of n limited nodes. If you use a picture to represent it, you can see that it looks like an upside-down tree. Therefore, we collectively call this type of data structure a tree, with the roots at the top and the leaves at the bottom. A general tree has the following characteristics:

• Each node has 0 or more child nodes

• The node without a parent node is called the root Node

• Each non-root node has and has only one parent node

• Each child node can be divided into multiple disjoint children Tree

The definition of a binary tree is: each node has at most two child nodes. That is, each node can only have the following four situations:

• Both the left subtree and the right subtree are empty

• Only the left subtree exists Tree

• Only the right subtree exists

• Both the left subtree and the right subtree exist

binary search tree

Binary search tree is also called binary sorting tree. It is either an empty tree or a binary tree with the following properties:

• ## If its left subtree is not empty, then the values ​​of all nodes on the left subtree are less than the value of the root node. If its right subtree is not empty, then the values ​​of all nodes on the right subtree are greater than the value of the root node.

• Its left and right subtrees are also binary search trees respectively

List several common implementation methods in Python:

1. Use classes and recursive functions to implement

By defining a node class, including node values, left and right sub-nodes and other attributes, and then implementing operations such as insertion, search, and deletion through recursive functions. The code example is as follows:

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

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

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert(value, self.root)

    def _insert(self, value, node):
        if value < node.data:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert(value, node.left)
        elif value > node.data:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert(value, node.right)

    def search(self, value):
        if self.root is None:
            return False
        else:
            return self._search(value, self.root)

    def _search(self, value, node):
        if node is None:
            return False
        elif node.data == value:
            return True
        elif value < node.data:
            return self._search(value, node.left)
        else:
            return self._search(value, node.right)

    def delete(self, value):
        if self.root is None:
            return False
        else:
            self.root = self._delete(value, self.root)

    def _delete(self, value, node):
        if node is None:
            return node
        elif value < node.data:
            node.left = self._delete(value, node.left)
        elif value > node.data:
            node.right = self._delete(value, node.right)
        else:
            if node.left is None and node.right is None:
                del node
                return None
            elif node.left is None:
                temp = node.right
                del node
                return temp
            elif node.right is None:
                temp = node.left
                del node
                return temp
            else:
                temp = self._find_min(node.right)
                node.data = temp.data
                node.right = self._delete(temp.data, node.right)
        return node

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

2. Use list implementation

Use a list to store the elements of the binary search tree, and then implement insertion, search, and deletion through the positional relationship of the elements in the list Wait for operations. The code example is as follows:

class BST:
    def __init__(self):
        self.values = []

    def insert(self, value):
        if len(self.values) == 0:
            self.values.append(value)
        else:
            self._insert(value, 0)

    def _insert(self, value, index):
        if value < self.values[index]:
            left_child_index = 2 * index + 1
            if left_child_index >= len(self.values):
                self.values.extend([None] * (left_child_index - len(self.values) + 1))
            if self.values[left_child_index] is None:
                self.values[left_child_index] = value
            else:
                self._insert(value, left_child_index)
        else:
            right_child_index = 2 * index + 2
            if right_child_index >= len(self.values):
                self.values.extend([None] * (right_child_index - len(self.values) + 1))
            if self.values[right_child_index] is None:
                self.values[right_child_index] = value
            else:
                self._insert(value, right_child_index)

    def search(self, value):
        if value in self.values:
            return True
        else:
            return False

    def delete(self, value):
        if value not in self.values:
            return False
        else:
            index = self.values.index(value)
            self._delete(index)
            return True

    def _delete(self, index):
        left_child_index = 2 * index + 1
        right_child_index = 2 * index + 2
        if left_child_index < len(self.values) and self.values[left_child_index] is not None:
            self._delete(left_child_index)
        if right_child_index < len(self.values) and self.values[right_child_index] is not None:
            self

3. Use a dictionary to implement

The key of the dictionary represents the node value, and the value of the dictionary is a dictionary containing the left and right child nodes. The code example is as follows:

def insert(tree, value):
    if not tree:
        return {value: {}}
    elif value < list(tree.keys())[0]:
        tree[list(tree.keys())[0]] = insert(tree[list(tree.keys())[0]], value)
    else:
        tree[list(tree.keys())[0]][value] = {}
    return tree

def search(tree, value):
    if not tree:
        return False
    elif list(tree.keys())[0] == value:
        return True
    elif value < list(tree.keys())[0]:
        return search(tree[list(tree.keys())[0]], value)
    else:
        return search(tree[list(tree.keys())[0]].get(value), value)

def delete(tree, value):
    if not search(tree, value):
        return False
    else:
        if list(tree.keys())[0] == value:
            if not tree[list(tree.keys())[0]]:
                del tree[list(tree.keys())[0]]
            elif len(tree[list(tree.keys())[0]]) == 1:
                tree[list(tree.keys())[0]] = list(tree[list(tree.keys())[0]].values())[0]
            else:
                min_key = min(list(tree[list(tree.keys())[0]+1].keys()))
                tree[min_key] = tree[list(tree.keys())[0]+1][min_key]
                tree[min_key][list(tree.keys())[0]] = tree[list(tree.keys())[0]]
                del tree[list(tree.keys())[0]]
        elif value < list(tree.keys())[0]:
            tree[list(tree.keys())[0]] = delete(tree[list(tree.keys())[0]], value)
        else:
            tree[list(tree.keys())[0]][value] = delete(tree[list(tree.keys())[0]].get(value), value)
    return tree

Since the dictionary is unordered, this implementation may cause the binary search tree to be unbalanced, affecting the efficiency of insertion, search, and deletion operations.

4. Use stack to implement

Using stack (Stack) can implement a simple binary search tree, which can implement operations such as insertion, search, and deletion through iteration. The specific implementation process is as follows:

• Define a node class, including node value, left and right sub-nodes and other attributes.

• Define a stack and initially push the root node onto the stack.

• When the stack is not empty, take out the top element of the stack and operate on it: if the value to be inserted is less than the current node value, insert the value to be inserted as the left child node , and push the left child node onto the stack; if the value to be inserted is greater than the current node value, insert the value to be inserted as the right child node, and push the right child node onto the stack; if the value to be found or deleted is equal to the current node value, Then return or delete the node.

• After the operation is completed, continue to take the next node from the stack and operate until the stack is empty.

It should be noted that in this implementation, because the stack is used to store the process of traversing the tree, it may result in high memory usage. In addition, due to the characteristics of the stack, this implementation can only support depth-first traversal (Depth-First Search, DFS) and cannot support breadth-first search (BFS).

The following is a pseudocode example:

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

def insert(root, value):
    if not root:
        return Node(value)
    stack = [root]
    while stack:
        node = stack.pop()
        if value < node.data:
            if node.left is None:
                node.left = Node(value)
                break
            else:
                stack.append(node.left)
        elif value > node.data:
            if node.right is None:
                node.right = Node(value)
                break
            else:
                stack.append(node.right)

def search(root, value):
    stack = [root]
    while stack:
        node = stack.pop()
        if node.data == value:
            return True
        elif value < node.data and node.left:
            stack.append(node.left)
        elif value > node.data and node.right:
            stack.append(node.right)
    return False

def delete(root, value):
    if root is None:
        return None
    if value < root.data:
        root.left = delete(root.left, value)
    elif value > root.data:
        root.right = delete(root.right, value)
    else:
        if root.left is None:
            temp = root.right
            del root
            return temp
        elif root.right is None:
            temp = root.left
            del root
            return temp
        else:
            temp = root.right
            while temp.left is not None:
                temp = temp.left
            root.data = temp.data
            root.right = delete(root.right, temp.data)
    return root

The above is the detailed content of What are the methods to implement binary search tree in python. For more information, please follow other related articles on the PHP Chinese website!