Tree Representations | Data Structure | Pusan National University

중첩 리스트인덱스 0은 루트 값, 1은 왼쪽 부분 트리, 2는 오른쪽 부분 트리이며 빈 트리는 []다.

insert_left기존 왼쪽 부분 트리를 버리지 않고 새 노드의 왼쪽 부분 트리로 내린다.

노드와 참조각 노드가 key와 두 자식 노드의 참조를 가지며 빈 자식 노드는 None이다.

인덱스를 이어 붙이면 부분 트리를 차례로 내려간다

트리 a 아래에 b(d, e)와 c(f)가 있는 중첩 리스트에서 식을 바꾸면 리스트의 어느 부분을 꺼내는지와 그 부분이 나타내는 부분 트리가 바뀐다.

식

위는 중첩 리스트, 아래는 같은 트리 그림이다. 초록으로 감싼 부분이 식의 결과이고, 그림에서 초록으로 채운 원이 그 부분 트리의 루트, 옅은 초록 원이 나머지 노드다.

root = ["a", ["b", [], []], ["c", [], []]]에 insert_left(root, "x")를 실행한다. 단계를 옮기면 리스트와 트리가 한 줄씩 실행한 결과로 바뀐다.

실행 단계 0

위는 root의 현재 값과 그 단계에서 만든 변수, 아래는 root가 나타내는 트리다. 파란 점선 부분이 새로 만든 리스트, 초록 부분이 old_left다.

같은 트리를 BinaryTree 노드로 만들었다. 표현식을 바꾸면 루트에서 따라가는 참조와 도달한 노드, 결과가 바뀐다.

표현식

상자 하나가 노드이며 세 칸은 차례로 key와 두 자식 노드의 참조다. 화살표가 참조이고, None은 참조할 자식 노드가 없다는 뜻이다. 초록 화살표와 초록 테두리 상자가 표현식이 따라간 경로와 도달한 노드다.