Algorithm learned with Python 11th: Tree structure

#Algorithm learned in Python

Introduction

Implement the basic algorithm in Python to deepen your understanding of the algorithm. As the 11th bullet, we will deal with the tree structure.

Tree structure

Breadth-first search

・ It feels like looking at each level ・ If you find only one match, you can ** process it at high speed ** ・ Keeps all nodes in the middle of search ⇒ It consumes a lot of memory

Depth-first search

・ How to go to the limit and come back again (also called ** backtrack **) · Often used to find all answers (up to a certain depth) ・ Recursive processing is often used ・ There are 3 different routes (going, returning, passing)

Tree structure processing route

Breadth-first search

A rough image is shown below. The actual processing order is shown below for each node. As I wrote at the beginning, breadth-first is processed for each layer.

Depth-first search

A rough image is shown below. All three routes follow the rough image above, but they are categorized according to the timing of processing the nodes.

① Going order

Process each node before tracing its children

② Return order

Process that node after tracing all the children of each node

③ Passing order

It processes after tracing the child node on the left side of the binary tree, and follows the child node on the right side.

Implementation

It is implemented in python, but for the sake of simplicity, the tree structure is represented by a list. The correspondence is as follows.

The following shows a simple implementation sample code for breadth-first search and depth-first search and the output at that time.

Code (breadth-first search)

breadth_search.py

"""
2020/12/29
@Yuya Shimizu

Breadth-first search
"""

tree = [[1,2], [3,4], [5,6], [7,8], [9,10], [11,12],
            [13,14], [], [], [], [], [], [], [], []]

data = [0]
while len(data) > 0:
    pos = data.pop(0) #pop:Extract 0 from data (0 disappears from data)
    print(pos, end = ' ')
    for i in tree[pos]:
        data.append(i)

output

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

By comparing with the above figure, it can be seen that the processing is performed in the order of breadth-first search.

Code (depth-first search: order of destination)

depth_search1.py

"""
2020/12/29
@Yuya Shimizu

Depth-first search 1: Going order
"""

tree = [[1,2], [3,4], [5,6], [7,8], [9,10], [11,12],
            [13,14], [], [], [], [], [], [], [], []]


def search(pos):
    print(pos, end = ' ')      #Output before examining the nodes under it
    for i in tree[pos]:        #Examine the nodes under it
        search(i)       #Search recursively

search(0)

output

0 1 3 7 8 4 9 10 2 5 11 12 6 13 14 

By comparing with the above figure, it can be seen that the depth-first search is processed in the order of destination.

Code (Depth-first search: Return order)

depth_search2.py

"""
2020/12/29
@Yuya Shimizu

Depth-first search 2: Return order
"""

tree = [[1,2], [3,4], [5,6], [7,8], [9,10], [11,12],
            [13,14], [], [], [], [], [], [], [], []]


def search(pos):
    for i in tree[pos]:        #Examine the nodes under it
        search(i)              #Search recursively
    print(pos, end = ' ')      #Output after examining the nodes under it

search(0)

output

7 8 3 9 10 4 1 11 12 5 13 14 6 2 0  

By comparing with the above figure, it can be seen that the depth-first search is processed in the return order.

Code (Depth-first search: Passing order)

depth_search3.py

"""
2020/12/29
@Yuya Shimizu

Depth-first search 3: Passing order
"""

tree = [[1,2], [3,4], [5,6], [7,8], [9,10], [11,12],
            [13,14], [], [], [], [], [], [], [], []]


def search(pos):
    if len(tree[pos]) == 2:       #When there are two children
        search(tree[pos][0])
        print(pos, end = ' ')       #Output between the left node and the right node
        search(tree[pos][1])
    elif len(tree[pos]) == 1:    #When there is one child
        search(tree[pos][0])
        print(pos, end = ' ')       #Output after examining the node on the left
    else:                               #When there is no subordinate node
        print(pos, end = ' ')

search(0)

output

7 3 8 1 9 4 10 0 11 5 12 2 13 6 14  

By comparing with the above figure, it can be seen that the processing is performed in the order of depth-first search.

Impressions

It was good to know how to use pop () in the code this time. It was also found that there are three different search routes for the tree structure, especially in the depth-first search, depending on the timing. Here, I ran the sample program and confirmed only the operation of the algorithm, but since I learned that it may also be used when making decisions on robots, I hope to implement it in the future.

References

Introduction to algorithms starting with Python: Standards and computational complexity learned with traditional algorithms Written by Toshikatsu Masui, Shoeisha