2020年6月13日土曜日

Go - Go Packages, Algorithms, and Data Structures - binary tree, find, delete

Go Systems Programming: Master Linux and Unix system level programming with Go (Mihalis Tsoukalos(著)、Packt Publishing)のChapter 4(Go Packages, Algorithms, and Data Structures)、Exercises 5.の解答を求めてみる。

コード

```package main

import (
"fmt"
"math/rand"
"time"
)

type tree struct {
value       int
left, right *tree
}

func insert(t *tree, v int) *tree {
if t == nil {
return &tree{v, nil, nil}
}
if v == t.value {
return t
}
if v < t.value {
t.left = insert(t.left, v)
return t
}
t.right = insert(t.right, v)
return t
}
func find(t *tree, v int) bool {
if t == nil {
return false
}
if t.value == v {
return true
}
if v < t.value {
return find(t.left, v)
}
return find(t.right, v)
}

func merge(tLeft, tRight *tree) *tree {
if tLeft == nil {
return tRight
}
if tRight == nil {
return tLeft
}
return &tree{tLeft.value, tLeft.left, merge(tLeft.right, tRight)}
}
func delete(t *tree, v int) *tree {
if t == nil {
return t
}
if t.value == v {
return merge(t.left, t.right)
}
if v < t.value {
t.left = delete(t.left, v)
return t
}
t.right = delete(t.right, v)
return t
}
func traverse(t *tree) {
if t == nil {
return
}
traverse(t.left)
fmt.Print(t.value, " ")
traverse(t.right)
}

func create(n int) *tree {
var t *tree
rand.Seed(time.Now().UnixNano())
for i := 0; i < 2*n; i++ {
t = insert(t, rand.Intn(n))
}
return t
}
func traverseln(t *tree) {
traverse(t)
fmt.Println()
}
func main() {
n := 30
t := create(n)
traverseln(t)
fmt.Println("The value of the root of the tree is", t.value)
for i := 0; i < 10; i++ {
fmt.Println(i, find(t, i))
}
for i := 0; i < 10; i++ {
traverseln(t)
k := rand.Intn(n)
t = delete(t, k)
fmt.Println("delte", k)
traverseln(t)
fmt.Println()
}
}
```

```% go build tree.go
% ./tree
0 1 2 3 4 5 6 7 8 9 10 12 13 14 16 17 18 19 20 21 22 23 24 26 27 28 29
The value of the root of the tree is 22
0 true
1 true
2 true
3 true
4 true
5 true
6 true
7 true
8 true
9 true
0 1 2 3 4 5 6 7 8 9 10 12 13 14 16 17 18 19 20 21 22 23 24 26 27 28 29
delte 25
0 1 2 3 4 5 6 7 8 9 10 12 13 14 16 17 18 19 20 21 22 23 24 26 27 28 29

0 1 2 3 4 5 6 7 8 9 10 12 13 14 16 17 18 19 20 21 22 23 24 26 27 28 29
delte 29
0 1 2 3 4 5 6 7 8 9 10 12 13 14 16 17 18 19 20 21 22 23 24 26 27 28

0 1 2 3 4 5 6 7 8 9 10 12 13 14 16 17 18 19 20 21 22 23 24 26 27 28
delte 0
1 2 3 4 5 6 7 8 9 10 12 13 14 16 17 18 19 20 21 22 23 24 26 27 28

1 2 3 4 5 6 7 8 9 10 12 13 14 16 17 18 19 20 21 22 23 24 26 27 28
delte 6
1 2 3 4 5 7 8 9 10 12 13 14 16 17 18 19 20 21 22 23 24 26 27 28

1 2 3 4 5 7 8 9 10 12 13 14 16 17 18 19 20 21 22 23 24 26 27 28
delte 18
1 2 3 4 5 7 8 9 10 12 13 14 16 17 19 20 21 22 23 24 26 27 28

1 2 3 4 5 7 8 9 10 12 13 14 16 17 19 20 21 22 23 24 26 27 28
delte 20
1 2 3 4 5 7 8 9 10 12 13 14 16 17 19 21 22 23 24 26 27 28

1 2 3 4 5 7 8 9 10 12 13 14 16 17 19 21 22 23 24 26 27 28
delte 6
1 2 3 4 5 7 8 9 10 12 13 14 16 17 19 21 22 23 24 26 27 28

1 2 3 4 5 7 8 9 10 12 13 14 16 17 19 21 22 23 24 26 27 28
delte 17
1 2 3 4 5 7 8 9 10 12 13 14 16 19 21 22 23 24 26 27 28

1 2 3 4 5 7 8 9 10 12 13 14 16 19 21 22 23 24 26 27 28
delte 4
1 2 3 5 7 8 9 10 12 13 14 16 19 21 22 23 24 26 27 28

1 2 3 5 7 8 9 10 12 13 14 16 19 21 22 23 24 26 27 28
delte 29
1 2 3 5 7 8 9 10 12 13 14 16 19 21 22 23 24 26 27 28

% ./tree
0 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29
The value of the root of the tree is 2
0 true
1 true
2 true
3 true
4 true
5 false
6 true
7 true
8 true
9 true
0 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29
delte 24
0 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 25 26 27 29

0 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 25 26 27 29
delte 21
0 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 22 23 25 26 27 29

0 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 22 23 25 26 27 29
delte 26
0 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 22 23 25 27 29

0 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 22 23 25 27 29
delte 21
0 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 22 23 25 27 29

0 1 2 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 22 23 25 27 29
delte 9
0 1 2 3 4 6 7 8 10 11 12 13 14 15 16 17 18 19 20 22 23 25 27 29

0 1 2 3 4 6 7 8 10 11 12 13 14 15 16 17 18 19 20 22 23 25 27 29
delte 29
0 1 2 3 4 6 7 8 10 11 12 13 14 15 16 17 18 19 20 22 23 25 27

0 1 2 3 4 6 7 8 10 11 12 13 14 15 16 17 18 19 20 22 23 25 27
delte 20
0 1 2 3 4 6 7 8 10 11 12 13 14 15 16 17 18 19 22 23 25 27

0 1 2 3 4 6 7 8 10 11 12 13 14 15 16 17 18 19 22 23 25 27
delte 22
0 1 2 3 4 6 7 8 10 11 12 13 14 15 16 17 18 19 23 25 27

0 1 2 3 4 6 7 8 10 11 12 13 14 15 16 17 18 19 23 25 27
delte 26
0 1 2 3 4 6 7 8 10 11 12 13 14 15 16 17 18 19 23 25 27

0 1 2 3 4 6 7 8 10 11 12 13 14 15 16 17 18 19 23 25 27
delte 19
0 1 2 3 4 6 7 8 10 11 12 13 14 15 16 17 18 23 25 27

%
```