[이산수학]연결리스트로 구현한 이진 트리

[이산수학]연결리스트로 구현한 이진 트리

배열로 편향 이진 트리를 구현하면 메모리의 낭비가 발생합니다. 이런 문제는 연결리스트로 해결할 수 있습니다. 

 

■ 연결리스트로 구현한 이진 트리

연결리스트는 부모 노드와 자식 노드를 주소로 연결하기 때문에 연속된 메모리 영역이 아니더라도 부모와 자식 노드를 연결할 수 있습니다. 

 

 

연결리스트는 왼쪽 노드와 오른쪽 노드를 가리키는 포인터 영역과 데이터를 저장하는 데이터 영역으로 구성됩니다. 하지만 잎 노드의 경우 자식 노드를 갖기 않기 때문에 자식 노드 주소가 null로 채워집니다. 

 

■ 연결리스트로 구현된 완전 이진 트리 / 편향 이진 트리 

 

연결리스트는 부모 노드와 자식 노드 간에 주소(포인터)로 연결되어 있기 때문에 편향 이진 트리라 하더라도 메모리를 낭비하지 않고 구현할 수 있습니다. 또한 부모 노드의 주소 영역만 변경하면 노드를 삽입하거나 삭제할 수 있기 때문에 배열로 구현한 이진 트리에 비해 훨씬 효율적입니다. 

 

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

 

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

이산수학 총정리

목록 보러가기 

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