최근 Rust로 이진 트리 자료구조를 구현해 보려 했다. 각 이진 트리는 루트 값과 왼쪽, 오른쪽 서브트리를 가진다. 꽤 직관적인 다음 Python 구현에서 출발했다.

class Tree:
  def __init__(self, val, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right

이렇게 하면 멋진 트리 객체를 다음과 같이 선언할 수 있다.

t = Tree(15,
      Tree(12,
           None,
           Tree(13)),
      Tree(22,
           Tree(18),
           Tree(100)))

그리고 그 결과는 아름답게 시각화할 수 있다.
(네, 제가 직접 그린 겁니다.)

그 코드를 Rust로 포팅하는 일은 조금… 까다로웠다. 첫 시도는 꽤 무해해 보였다.

struct Tree {
  root: i64,
  left: Tree,
  right: Tree,
}

Python 정의를 거의 일대일로 옮긴 것이나 다름없지만 — rustc 는 안 된다고 한다.

error[E0072]: recursive type `Tree` has infinite size
 --> src/main.rs:1:1
  |
1 | struct Tree {
  | ^^^^^^^^^^^ recursive type has infinite size
  |
  = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `Tree` representable

Python, PHP, Ruby 같은 메모리 관리 언어에 익숙했던 나는 이 오류가 당황스러웠다. 하지만 문제는 이해하기 쉽다. 컴퓨터의 메모리는 한정되어 있다. 각 항목에 얼마나 많은 메모리를 할당할지 알아내는 것은 컴파일러의 몫이다.

우리의 경우 컴파일러는 다음과 같이 추론한다.

트리는 i64 하나와 두 개의 트리를 담는 구조체다. 이 트리들 각각은 다시 i64 하나와 두 개의 트리를 담는 구조체다. 각각의…
대충 무슨 말인지 알 것이다.

Tree { i64, Tree, Tree }
Tree { i64, Tree { ... }, Tree { ... } }
// The next expansion won't fit on the page anymore

트리에 서브트리가 몇 개 있을지 알 수 없으니, 미리 얼마나 많은 메모리를 할당해야 할지 알 방법이 없다. 실행 시점이 되어서야 알 수 있다!

Rust는 해결 방법을 알려준다. Box, Rc 또는 & 같은 간접 참조(indirection)를 넣으라는 것이다. 이들은 Rust의 서로 다른 “포인터 타입”이다. 모두 메모리의 어딘가를 가리킨다. 그래서 트리 구조체 전체 크기를 알 필요 없이, 트리가 위치한 메모리상의 지점만 알면 된다. 하지만 이것만으로도 트리 구조를 정의하기에 충분하다. 이 포인터 타입들을 이용하면 수동 메모리 관리 없이도 안전하게 이를 구현할 수 있다. 각각 다른 보장을 제공하므로 요구에 가장 잘 맞는 것을 선택해야 한다.

• &는 Rust에서 borrow라고 부른다. 세 가지 중 가장 흔하다. 메모리의 어딘가를 참조하지만, 가리키는 데이터를 소유하지는 않는다. 따라서 borrow의 수명은 소유자에 따라 달라진다. 그러므로 여기서는 수명 매개변수를 추가해야 한다. 이 때문에 사용이 번거로워질 수 있다.

  struct Tree<'a> {
    root: i64,
    left: &'a Tree<'a>,
    right: &'a Tree<'a>,
  }

• Box는 런타임 오버헤드가 없는 스마트 포인터다. 가리키는 데이터를 소유하며 힙에 저장한다. 스코프를 벗어날 때 가리키던 데이터를 먼저 drop하고 자신을 해제하기 때문에 스마트하다고 부른다. 수동 메모리 관리가 필요 없다는 점이 깔끔하다. ✨

  struct Tree {
    root: i64,
    left: Box<Tree>,
    right: Box<Tree>,
  }

• Rc는 또 다른 스마트 포인터다. “reference-counting(참조 카운팅)”의 약자다. 내부적으로 자료구조에 대한 참조 수를 추적한다. 참조 수가 0이 되는 즉시 스스로 정리한다. 한 스레드 내에서 같은 데이터에 대해 여러 소유자가 필요하다면 Rc를 선택하자. 멀티스레딩을 위해서는 Arc(atomic reference count)도 있다.

  struct Tree {
    root: i64,
    left: Rc<Tree>,
    right: Rc<Tree>,
  }

트리를 Box에 넣기

세 가지 방법 모두 완전히 유효하다. 어떤 것을 선택해야 할지는 사용 사례에 따라 다르다. 경험상 단순하게 유지하는 것이 좋다. 내 경우에는 특별한 보장이 필요하지 않았기 때문에 Box를 선택했다.

서브트리를 선택 사항으로 만들기

다음으로 마주한 문제는 트리 구조체를 인스턴스화할 수 없다는 것이었다. 왼쪽과 오른쪽 서브트리의 타입이 Box<Tree>인데, 어느 시점에서는 빈 서브트리가 필요하기 때문이다.

Python 예제에서는 자료구조의 끝을 나타내기 위해 None을 사용했다. Rust의 Option 타입 덕분에 같은 방식을 쓸 수 있다.

struct Tree {
  root: i64,
  left: Option<Box<Tree>>,
  right: Option<Box<Tree>>,
}

이 모든 과정을 거치면 첫 번째 트리를 만들 수 있다.

Tree {
    root: 15,
    left: Some(Box::new(Tree {
            root: 12,
            left: None,
            right: Some(Box::new(Tree {
                    root: 13,
                    left: None,
                    right: None,
            })),
    })),
    right: Some(Box::new(Tree {
            root: 22,
            left: Some(Box::new(Tree {
                    root: 18,
                    left: None,
                    right: None,
            })),
            right: Some(Box::new(Tree {
                    root: 100,
                    left: None,
                    right: None,
            })),
    })),
};

관점에 따라 이것이 장황하다고 할 수도, 명시적이라고 할 수도 있다. Python 버전에 비하면 내 취향에는 조금 복잡해 보였다.

더 나은 방법은 없을까? Chris McDonald가 다음 표현을 함께 고민해 줬다.

Tree::new(15)
  .left(
    Tree::new(12)
      .right(Tree::new(13))
  )
  .right(
    Tree::new(22)
      .left(Tree::new(18))
      .right(Tree::new(100))
  );

개인적으로는 이쪽이 훨씬 보기 편하다.
이를 가능하게 하는 전체 트리 구현은 다음과 같다.

#[derive(Default)]
struct Tree {
  root: i64,
  left: Option<Box<Tree>>,
  right: Option<Box<Tree>>,
}

impl Tree {
  fn new(root: i64) -> Tree {
    Tree {
      root: root,
      ..Default::default()
    }
  }

  fn left(mut self, leaf: Tree) -> Self {
    self.left = Some(Box::new(leaf));
    self
  }

  fn right(mut self, leaf: Tree) -> Self {
    self.right = Some(Box::new(leaf));
    self
  }
}

업데이트: Danny Grein이 트위터에서 From<i64> for Tree를 구현하면 다음 구문을 지원할 수 있다고 언급했다.

root(15)
  .left(
    root(12)
      .right(13)
   )
  .right(
    root(22)
      .left(18)
      .right(100)
  );

왜 Python에서는 그냥 잘 됐을까?

이제 왜 Python에서는 트리 구현이 아무 문제 없이 잘 동작했는지 궁금할 것이다. 이유는 Python이 런타임에 트리 객체를 위한 메모리를 동적으로 할당하기 때문이다. 또한 모든 것을 PyObject로 감싸는데, 이는 위에서 본 Rc와 비슷한 — 참조 카운팅 스마트 포인터다.

Rust는 이 부분에서 더 명시적이다. 우리의 필요를 표현할 더 많은 유연성을 주지만, 이를 잘 활용하려면 가능한 모든 대안을 알아야 한다. 간단한 borrow로 충분하다면 스마트 포인터는 피하라는 것이 내 조언이다.

하지만 수명(lifetime)이 걸림돌이 되거나 스레드 안전성 같은 추가 보장이 필요하다면, 스마트 포인터는 툴킷에 추가할 훌륭한 도구다. 스마트 포인터에 대해 더 배우고 싶다면 Rust 공식 문서가 좋은 출발점이다. 또한 트리를 런타임에 가변적으로 만들어야 하는 경우, 할당자(allocator)를 영리하게 활용하는 방법에 대해서는 “Idiomatic tree and graph-like structures in Rust”를 읽어보길 권한다.