V language : Binary Search Tree (BST)

Binary Search Tree

이진 탐색 트리

1. 문법 살펴보기

1. V에는 null type이 없다. (제일 힘들었다.)

 

2. try/catch/block

V 언어에서는 try/catch/null이 다 없는데, or 키워드가 있다.

아래 코드를 보면 user := repo.find~(10) or { 이 있는데,

이 부분은, 함수를 만들 때 우선 ? 키워드를 사용하여 option type이라고 지정해야 하고,

사용할 때는 or { // 실패했을 때 // } 와 같이 사용해야한다.

struct User {
    id int
    name string
}

struct Repo {
    users []User
}

fn (r Repo) find_user_by_id(id int) ?User {
    for user in r.users {
        if user.id == id {
            // V automatically wraps this into an option type
            return user
        }
    }
    return error('User $id not found')
}

fn main() {
    repo := Repo {
        users: [User{1, 'Andrew'}, User {2, 'Bob'}, User {10, 'Charles'}]
    }
    user := repo.find_user_by_id(10) or { // Option types must be handled by `or` blocks
        return
    }
    println(user.id) // "10"
    println(user.name) // "Charles"
}

 

2. BST 구현

1. null 타입을 확인할 수가 없기 때문에, ptr_str (0x0)을 이용했다.

// tree.left가 ptr_str(0x0)가 아니면 true, 맞으면 false
a := tree.left.exist()

fn (t &Tree) exist() bool {
    if t == &Tree(0) {
        return false
    }
    return true
}

 

Full source

struct Tree {
    value int
mut:
    left &Tree = &Tree(0)
    right &Tree = &Tree(0)
}

/*
    BST (Binary Search Tree)

1. its value is strictly greater than the values of every node to its left
2. its value is less than or equal to the values of every node to its right
*/
fn main() {
    mut tree := &Tree{value: 30}  // root

    nodes := [15, 60, 7, 22, 45, 75, 17, 27]

    for node in nodes {
        tree.insert(node)
    }

    println(tree.value)  // 30
    println(tree.left.value)  // 15
    println(tree.left.right.value)  // 22
    println(tree.left.right.right.value)  // 27
    println(tree.left.right.left.value)  // 17
    println(tree.left.left.value)  // 7

    println(tree.right.value)  // 60
    println(tree.right.left.value)  // 45
    println(tree.right.right.value)  // 75
}

fn (mut t Tree) insert(val int) &Tree {
    // println(t.str())
    if val < t.value {
        if t.left.exist() {
            return t.left.insert(val)
        } else {
            t.left = &Tree{value: val}
        }
    } else {
        if t.right.exist() {
            return t.right.insert(val)
        } else {
            t.right = &Tree{value: val}
        }
    }

    return t
}

fn (t &Tree) exist() bool {
    if t == &Tree(0) {
        return false
    }
    return true
}

// Node print
fn (t &Tree) str() string {
        return 'Node {\n' +
    '   value: $t.value\n' +
    '   left: 0x${ptr_str(t.left)}\n' +
    '   right: 0x${ptr_str(t.right)}\n' +
    '}'
}

 

3. 참고

(개인) Github Algorithms in V language : https://github.com/Alfex4936/V-algorithms

Alfex4936/V-algorithms