데이터 저장과 탐색 방식의 차이지

너의 예시대로 짯을 경우를 생각해보면

이중연결리스트는 바로 전 데이터를 한번에 찾아갈수 있음

하지만 트리는 부모노드를 찾아 갈 수 있을까?

(개소리)

-----

두개는 비교의 대상이 아님

굳이 비교하자면 이중연결리스트가아닌 일반 리스트와 트리를 비교하는게 맞아

리스트라는 저장방법을 이용해서 트리라는 탐색하는 방법을 사용한다고 보는게 이해가 쉬우려나

굳이 비교를 하자면 (일반적인)리스트는 다음 한개의 노드에 대한 정보만을 저장하는 선형이고 트리는 다음 한개이상의 노드를 가지고 있는 비선형구조임

연결방식이 다름.

이중연결리스트는 선행과 후행을 모두 연결해 앞뒤로 쉬이 움직임.

하지만 일반 이진트리는 자기 자식만 2개 가지고 있기에 자식이 부모를 찾으려면 따로 저장하지 않는 한 루트부터 다시 탐색해야 함.

님이 제시한 코드는 방구석 컴공이 볼때는

예전이라 정확하게 기억은 안나는데

이중리스트는 맞는 구조인데

트리는

2진트리에 부모노드 없는 구조인거 같은디요?

원래 트리에 부모노드 없었나??

전혀 다름.

이중 연결 리스트(보통 이중 연결 리스트라고 안부르고 양방향 연결리스트라고 부름)는

앞 뒤로 움직이는 거라서 앞으로도 접근할 수 있고 뒤로도 접근할 수 있음.

예를 들어 이렇게 연결리스트가 구현되어 있다고 할 때,

A-B-C-D

B에서는 A도 갈 수 있고 C도 갈 수 있음. 그야말로 양방향 연결임.

그러나 일반적인 이진 트리는 검색을 하기 위해서는 무조건 루트부터 시작해서 들어가야만 함.

즉, 어떤 노드 A가 자기보다 상위의 있는 노드로 바로 접근이 안됨.

위의 예를 트리로 구현한다 치면

A(level 1)

│

B(level 2)

│

C(level 3)

│

D(level 4)

이렇게 그냥 줄줄이 땅콩처럼 연결되어 있다고 가정하자.

그럼 B에서는 C로는 갈 수 있지만 A로는 못 감.

C에서는 D로 갈 수 있지만 B로는 못 감. C에서 B로 가려면 A->B 이렇게 접근할 수 밖에 없음.