[Introduction] I tried to implement it by myself while explaining the binary search tree.

[Introduction] I tried to implement it by myself while explaining the binary search tree.

Purpose

• I want to deepen my understanding of data structures and algorithms by studying binary search trees.
• Implement a binary search tree and data structure in python.
• It may be easier to implement if you fold the data structure into a one-dimensional list, but to deepen your understanding of the tree data structure, dare to define a node class and implement a binary search tree.

Contents

Definition of binary search tree

A binary search tree is a binary tree data structure having the values of nodes whose order relations are defined (such as numerical values and characters with defined permutations). 　 For the tree structure, see here (https://qiita.com/tagtagtag/items/c5c460633e1ac864937a).

Each node has 0, 1 and 2 child nodes, and the one with a smaller value is defined as a left child node and the one with a larger value is defined as a right child node.

As far as I investigated, I could not confirm the exact definition of the node with the same value, so I will include it in the right child node in this article.

Please note that there is a method to remove duplicates in some cases.

Binary Search Tree Properties

Due to the above definition, values smaller than the vertex node are stored in the left branch, and values larger than the vertex node are stored in the right branch. This structure is maintained regardless of the position of the binary search tree.

In addition, the left end of the tree has the minimum value of the set, and the right end has the maximum value.

Furthermore, when the node value is output in the inode traversal, the set is sorted in ascending order and output.

See Wiki Binary Search Tree

• To avoid misunderstanding, 13 in this figure is not at the right end. The right end is 14. 13 is not a right child node because it is a left child of 14 nodes.

Implementation

A Node class was defined to implement the data structure of the binary search tree.

The Node class has the values of self.data and the left child self.left right child self.right as the values of the node. The default left and right children are None.

A BST class was defined for the implementation of the binary search tree.

In the constructor, I defined self.root and set the default to None. Also, self.insert (val) is executed to add a new node. The method introduction is shown below.

Implemented the following as a method See the code for details.

• Add a node
• Check for the presence of a node with a certain value
• Get the minimum value
• Get maximum
• Output the value with inoder

I found the following points to be interesting in this data structure.

• In the binary search tree, the point is to start from the route and sort left and right according to the value.
• If a note is stored at the destination, it will go deeper from that point.
• When you reach the end, add it there.
• Miso is sorted in order from the top.

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


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

        for val in arr:
            self.insert(val)
    
    def insert(self, val):
        if self.root is None:
            self.root = Node(val)

        else:
            node = self.root
            flag = True

            while flag:
                if node.data > val:
                    if node.left is None:
                        node.left = Node(val)
                        flag = False 
                        #Set False to end while
                    else:
                        node = node.left
                else:
                    if node.right is None:
                        node.right = Node(val)
                        flag = False
                    else:
                        node = node.right


    def find(self, node, val):
        if node is not None:
            if node.data == val:
                return True

            else:
                flag_left = self.find(node.left, val) 
                flag_right = self.find(node.right, val)
            
                if flag_left or flag_right:
                    return True

        return False

    def bst_min(self, node):
        if node.left is None:
            return node.data
        else:
           return self.bst_min(node.left) 
           #If you want to return the value that you arrived at by recursion, write a recursive function after return. Please note that the usage is different from that of traversal.
        
    def bst_max(self, node):
        if node.right is None:
            return node.data
        else:
            return self.bst_max(node.right)

    def inoder_traverse(self, node):
        if node is not None:
            self.inoder_traverse(node.left)
            print(node.data)
            self.inoder_traverse(node.right)

Run

Executed as follows

import random

arr = [random.randint(1, 100) for _ in range(12)]
ins = BST(arr)
print('insert node list =>', arr)
print('Is there No.4 ->', ins.find(ins.root, 4))
print('root', ins.root.data)
print('min', ins.bst_min(ins.root))
print('max', ins.bst_max(ins.root))
print('--------------------------')
print('Sorted when output in the order of passing')
ins.inoder_traverse(ins.root)

result

The list that is inserted changes each time, so if you try it a few times, you will get a better understanding.

insert node list => [48, 10, 21, 58, 61, 12, 5, 87, 35, 2, 7, 39]
Is there No.4 -> False
root 48
min 2
max 87
--------------------------
Sorted when output in the order of passing
2
5
7
10
12
21
35
39
48
58
61
87

References

• Introduction to Data Structures and Algorithms (O'Reilly)
• [Explanation of the binary tree by Wikipedia](https://ja.wikipedia.org/wiki/%E6%9C%A8%E6%A7%8B%E9%80%A0_(%E3%83%87%E3) % 83% BC% E3% 82% BF% E6% A7% 8B% E9% 80% A0))