[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

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

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.

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


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

Recommended Posts

[Introduction] I tried to implement it by myself while explaining the binary search tree.
[Introduction] I tried to implement it by myself while explaining to understand the binary tree
A super introduction to Django by Python beginners! Part 6 I tried to implement the login function
I tried to analyze the New Year's card by myself using python
I tried to optimize while drying the laundry
I tried to implement the traveling salesman problem
I tried to rescue the data of the laptop by booting it on Ubuntu
I tried LeetCode every day 108. Convert Sorted Array to Binary Search Tree (Python, Go)
I tried to implement PCANet
I tried to implement StarGAN (1)
I tried to implement anomaly detection by sparse structure learning
[Introduction to simulation] I tried playing by simulating corona infection ♬
[Django] I tried to implement access control by class inheritance.
[Introduction to Pandas] I tried to increase exchange data by data interpolation ♬
I tried to implement the mail sending function in Python
I tried to implement Deep VQE
I tried to make it possible to automatically send an email just by double-clicking the [Python] icon
[Introduction to simulation] I tried playing by simulating corona infection ♬ Part 2
I tried to visualize the Beverage Preference Dataset by tensor decomposition.
I tried to implement adversarial validation
I tried to implement sentence classification by Self Attention with PyTorch
I tried to summarize the commands used by beginner engineers today
I tried to predict by letting RNN learn the sine wave
I tried to implement hierarchical clustering
I tried to solve the shift scheduling problem by various methods
I tried to implement Realness GAN
Try to implement and understand the segment tree step by step (python)
I tried to move the ball
I tried to estimate the interval.
A super introduction to Django by Python beginners! Part 3 I tried using the template file inheritance function
A super introduction to Django by Python beginners! Part 2 I tried using the convenient functions of the template
I tried to make it possible to automatically send an email just by double-clicking the [GAS / Python] icon
I tried moving the image to the specified folder by right-clicking and left-clicking
When I tried to run Python, it was skipped to the Microsoft Store
I tried to summarize the general flow up to service creation by self-education.
765 I tried to identify the three professional families by CNN (with Chainer 2.0.0)
I tried to implement Bayesian linear regression by Gibbs sampling in python
Matching karaoke keys ~ I tried to put it on Laravel ~ <on the way>
I tried to find the optimal path of the dreamland by (quantum) annealing
I tried to verify and analyze the acceleration of Python by Cython
I tried to understand the decision tree (CART) that makes the classification carefully
I tried to summarize the Linux commands used by beginner engineers today-Part 1-
I tried to solve the inverted pendulum problem (Cart Pole) by Q-learning.
I tried to verify the result of A / B test by chi-square test
I tried to implement PLSA in Python
I tried to implement Autoencoder with TensorFlow
I tried to summarize the umask command
I tried to implement permutation in Python
I tried to recognize the wake word
I tried to implement PLSA in Python 2
I tried to summarize the graphical modeling.
I tried to implement ADALINE in Python
I tried to estimate the pi stochastically
I tried to touch the COTOHA API
I tried to implement PPO in Python
I tried to implement CVAE with PyTorch
I want to read CSV line by line while converting the field type (while displaying the progress bar) and process it.
python Binary search It is surprisingly easy to implement bisect.bisect_left and bisect.bisect_right from 0
When I tried to change the root password with ansible, I couldn't access it.
I tried to verify the Big Bang theorem [Is it about to come back?]
I tried to predict the presence or absence of snow by machine learning.