트리(Tree) 자료구조를 공부하다 보면 반드시 마주치게 되는 개념이 바로 노드(Node)입니다. 트리를 구성하는 모든 요소가 노드이기 때문에, 이진 트리(Binary Tree)를 정의하기 전에 먼저 노드가 무엇인지 명확히 이해해야 합니다.
노드의 기본 구조
노드는 크게 세 가지 속성(property)으로 정의할 수 있습니다.
left — 현재 노드의 왼쪽 자식 노드에 대한 참조(reference)를 저장합니다.
right — 현재 노드의 오른쪽 자식 노드에 대한 참조를 저장합니다.
data — 해당 노드에 저장하고자 하는 데이터를 담습니다.
자바스크립트로 노드 클래스 구현하기
위에서 설명한 구조를 자바스크립트 코드로 표현하면 다음과 같습니다.
class Node {
constructor(data, left = null, right = null) {
this.data = data;
this.left = left;
this.right = right;
}
}위 코드는 data, left, right 세 가지 속성을 받는 생성자(constructor)를 통해 Node 데이터 구조를 정의한 것입니다. left와 right 매개변수에는 기본값으로 null이 지정되어 있어, 노드를 생성할 때 자식 노드 정보를 생략할 수 있습니다.
노드 생성 시 left와 right가 대부분 null인 이유
이진 트리에서는 일반적으로 리프(leaf) 위치에 값을 삽입하기 때문에, 노드를 새로 만들 때 left와 right 속성을 null로 설정하는 경우가 대부분입니다. 즉, 처음에는 자식이 없는 상태로 노드를 생성하고, 이후 트리에 삽입하는 과정에서 자식 참조가 채워지는 방식입니다.
BinarySearchTree 클래스 내부에 노드 정의하기
사용 편의성을 위해 Node 클래스를 별도로 두지 않고, 앞으로 만들 BinarySearchTree(이진 탐색 트리) 클래스의 내부 속성으로 정의하는 것이 좋습니다. 이렇게 하면 노드 정의가 실제로 사용되는 클래스 안에 함께 존재하게 되어 코드의 응집도가 높아지고 관리가 쉬워집니다.
참고: 다진 트리(Multiway Tree)의 경우
지금 살펴본 것처럼 left와 right라는 두 개의 명시적인 속성을 갖는 노드 구조는 이진 트리에 적합합니다. 반면 B-트리(B-tree)나 B+트리(B+ tree)처럼 하나의 노드가 여러 개의 자식을 가질 수 있는 다진 트리(multiway tree)에서는 left, right 대신 children이라는 속성을 정의하고, 여기에 배열(Array) 또는 그와 유사한 컨테이너 자료구조로 자식 노드들을 저장합니다.
이처럼 노드는 트리 자료구조의 가장 작은 빌딩 블록이며, 어떤 종류의 트리를 구현하느냐에 따라 노드의 구조 설계가 달라진다는 점을 기억해 두면 좋습니다.