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

Go Systems Programming:
Master Linux and Unix
system level programming with Go
楽天ブックス紀伊國屋書店

開発環境

macOS Catalina - Apple (OS)
Emacs (Text Editor)
Windows 10 Pro (OS)
Visual Studio Code (Text Editor)
Go (プログラミング言語)

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()
 }
}

入出力結果(Zsh、PowerShell、Terminal)

% 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 

%

Kamimura's blog

2020年6月13日土曜日

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

0 コメント:

コメントを投稿