[이산수학]배열로 구현한 이진 트리

[이산수학]배열로 구현한 이진 트리

 

■ 배열로 구현한 완전 이진 트리

- 각 노드 변호를 인덱스로 하여 1차원 배열로 구현할 수 있습니다.

- 노드 번호는 1부터 시작하므로 배열에서 인덱스가 0인 자리는 비워두고, 인덱스가 1인 자리부터 노드 값을 저장하면 됩니다. 

 

 

■ 배열로 구현한 편향 이진 트리

- 노드 인덱스는 완전 이진 트리처럼 왼쪽 자식 노드 인덱스는 2n, 오른쪽 자식 노드 인덱스는 2n+1입니다. 

- 편향 이진 트리를 구성하는 각 노드의 인덱스에 해당하는 배열의 영역에 노드 값이 들어갑니다. 

- 그래서 메모리 공간의 낭비가 발생합니다. 

 

 

■ 이진 트리에서 각 노드의 인덱스 규칙

- 레벨 1의 노드 인덱스 2번과 3번은 부모 노드인 1번의 2배 또는 2배에 1를 더한 것입니다. 

- 즉, 노드 인덱스의 n의 왼쪽 자식 노드 인덱스는 2n, 오른쪽 자식 노드 인덱스는 2n+1이 됩니다.

- 반대로 노드 인덱스 n의 부모 노드는 n을 2로 나누었을 때의 몫이 됩니다. 

 

 

■ 이진 트리를 배열로 구현할 경우

- 인덱스 규칙만 따르면 쉽게 탐색할 수 있습니다. 

- 삭제와 삽입이 비효율적입니다.

 

 

 

 

 

수학으로 이해하는 디지털 논리 이산수학 367p 참고

 

-----------------------------------

이산수학 총정리

목록 보러가기 

-----------------------------------