[RUST] 이진 트리 (Binary Tree) (feat.LSM Tree)

안녕하세요.

Nodes(빨간 벌)입니다.

 

주의

해당 글은 Rust를 공부하고 오늘 한 내용을 정리한 포스트입니다.

설명을 위한 글이 아닙니다.

 

오늘은

키-값 저장을 위한 이진트리(Binary Tree)를 Rust로 구현해봤습니다.

 

Rust는 다른 프로그래밍 언어와 다르게 소유권이라는 개념을 가지고 있어서

사용할 때마다 아차... 하는 실수들이 많이 발생하더라고요...

아직은 공부 단계라... 더 익숙하지 않아서 에러도 많이 나네요... 

 

#[derive(Debug)]
struct Element {
    key : String,
    val : String
}

 

노드에 저장될 값이 키-값 쌍인 데이터이기에

구조체 형식으로 선언해주었습니다.

 

 

아니... Rust는 코드 블록 지원이 안되잖아...

코드 블록 미지원으로 인해... 읽는데 불편하실 수도 있습니다...

죄송합니다..

 

 

#[derive(Debug)] 아래 구조체에 대한 디버깅 출력을 위해 선언해줍니다.

 

#[derive(Debug)]
struct Node<'a>{
    element : &'a Element,
    left : Option<Box<Node<'a>>>,
    right : Option<Box<Node<'a>>>,
    size : usize,
}

 

노드 구조체입니다.

LEFT와 RIGHT에 데이터 형을 지정해준 부분을 보시면

이진트리는 LEFT, RIGHT가 자식 노드들을 가리키고 있어야 합니다.

 

 

 Rust는 구조체가 자기 자신을 직접 가리키는 행위를 허락하지 않습니다. 

그렇기에 Box로 감싸주셔야 합니다.

 

 

fn new_tree(elements : &[ELement]) -> Option<Box<Node>> {
    let size : usize = elements.len();
    
    // elements 사이즈가 0 일때 None을 반환
    if size == 0 {
    	return None;
    }
    
    // elements 의 중간 값 구하고 그 값을 기준으로 left, right 에 할당
    let half = size / 2;
    let r_half = half + 1;
    let element = &elements[half];
    
    // left부분 재귀
    let left = new_tree(&elements[..half]);
    let mut right = None;
    if r_index < size {
    	// right부분 재귀
        right = new_tree(&elements[r_half..]);
    }
    
    // 노드 생성
    let root = Node{
    	element,
        left,
        right,
        size,
    };
    
    // 생성된 노드를 Box로 감싼 후 반환
    Some(Box::new(root))
}

 

트리 생성 코드입니다. 

 반환 값은 Option 이므로 Some이나 None을 반환받습니다.

위 코드를 보시면 size가 0일 때와 맨 아랫줄에 리턴되는 값을 보시면

None을 반환하거나 Some으로 감싼 형태를 반환합니다.

 

매개변수로 받은 elements들을 반으로 나눈 후 양쪽 노드로 할당해주는 코드입니다.

데이터베이스에 나오는 LSM트리 알고리즘과 Rust를 같이 공부하면서 짠 코드이기에

초점이 LSM트리 초석 구현에 맞춰져 있습니다.

 

fn main() {
    let test = [
    	Element{
            key : "1".to_string(),
            val : "one".to_string()
        },
        Element{
            key : "2".to_string(),
            val : "two".to_string()
        },
        Element{
            key : "3".to_string(),
            val : "three".to_string()
        }
    ];
    
    let node = new_tree(&test);
    println!("{:?}", node);
}

 

테스트 코드입니다.

 

 

위의 내용들은 이진트리에 대해 깊게 설명하는 내용이 아닙니다.

위에서 언급했듯이 Rust를 공부한 내용들을 정리해놓은 포스트입니다.