이중연결리스트의 구조체가
struct Node{
int data;
Node *prev;
Node *next;
}
요런식이고
트리 는
struct TreeNode{
int data;
TreeNode* left_child;
TreeNode* right_child;
};
결국 다음 노드에대한 정보를 저장하는건 같은거 아닌가요??
15개의 댓글
무분별한 사용은 차단될 수 있습니다.
이중연결리스트의 구조체가
struct Node{
int data;
Node *prev;
Node *next;
}
요런식이고
트리 는
struct TreeNode{
int data;
TreeNode* left_child;
TreeNode* right_child;
};
결국 다음 노드에대한 정보를 저장하는건 같은거 아닌가요??
Tbps
데이터 저장과 탐색 방식의 차이지
으챠
너의 예시대로 짯을 경우를 생각해보면
이중연결리스트는 바로 전 데이터를 한번에 찾아갈수 있음
하지만 트리는 부모노드를 찾아 갈 수 있을까?
(개소리)
-----
두개는 비교의 대상이 아님
굳이 비교하자면 이중연결리스트가아닌 일반 리스트와 트리를 비교하는게 맞아
리스트라는 저장방법을 이용해서 트리라는 탐색하는 방법을 사용한다고 보는게 이해가 쉬우려나
굳이 비교를 하자면 (일반적인)리스트는 다음 한개의 노드에 대한 정보만을 저장하는 선형이고 트리는 다음 한개이상의 노드를 가지고 있는 비선형구조임
뉘일
아하 감사합니다 연결리스트는 일직선상의 저장이지만 트리구조는 갈래로 뻗어나가서 부모노드를 찾을수없는경우가 있군요
으챠
내가 글을 막무가내로써거 순서가 이상한데 다시 말하자면
두개는 비교의 대상이 아님
리스트라는 저장방법을 이용해서 트리라는 탐색하는 방법을 사용한다고 보는게 내 생각임
그 이유는 일반적인 트리에서 바로 부모를 못찾아가는 문제가 있으니 부모노드의 정보를 자식노드에 저장하여 바로 이동하게 구현이 가능함
그래서 비교를 하기 어렵다는거임
굳이 비교하자면 이중연결리스트가아닌 일반 리스트와 트리를 비교하는게 맞아
(일반적인)리스트는 다음 한개의 노드에 대한 정보만을 저장하는 선형이고 트리는 다음 한개이상의 노드를 가지고 있는 비선형구조임
느그본체만수무강
연결방식이 다름.
이중연결리스트는 선행과 후행을 모두 연결해 앞뒤로 쉬이 움직임.
하지만 일반 이진트리는 자기 자식만 2개 가지고 있기에 자식이 부모를 찾으려면 따로 저장하지 않는 한 루트부터 다시 탐색해야 함.
뉘일
감사합니다!
점심추천해줘
님이 제시한 코드는 방구석 컴공이 볼때는
예전이라 정확하게 기억은 안나는데
이중리스트는 맞는 구조인데
트리는
2진트리에 부모노드 없는 구조인거 같은디요?
원래 트리에 부모노드 없었나??
뉘일
아이공.. 대충적었더니 죄송합니당
점심추천해줘
좀 더 들어가자면
노드 저장 구조가 다름
이중리스트는 옆으로 이동하는거라 다시 원점으로 돌아갈수 있는데
트리는 내려가는거라 다시 못 올라옴
저장되는거 잘 생각해보면
비유를 하자면
이중 리스트는
1005호 기준으로
1004호 10003호가 있고
1004호 기준으로
1003호 1005호가 있음
즉 1005호에서 시작해서 다시 1005호로 돌아갈수 있음
근데 트리는
1005호 기준
904호 903호가 있고
904호는 803호 805호가 있음
즉 한번 움직이면 다시는 못돌아옴
숨은음은
전혀 다름.
이중 연결 리스트(보통 이중 연결 리스트라고 안부르고 양방향 연결리스트라고 부름)는
앞 뒤로 움직이는 거라서 앞으로도 접근할 수 있고 뒤로도 접근할 수 있음.
예를 들어 이렇게 연결리스트가 구현되어 있다고 할 때,
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 이렇게 접근할 수 밖에 없음.
뉘일
아하.. 접근성에 차이군요 감사합니다
숨은음은
트리는 일종의 "다중 연결 리스트"라고 생각하면 편함.
원래 연결 리스트는 무조건 자기 다음 1개에 대한 노드만 연결되어 있잖아.
그게 2개인거임. 근데 구분을 지어야 하니까 왼쪽 다음 노드, 오른쪽 다음 노드.
그리고 여기에 그냥 그렇게 막 배치하면 정렬이 힘들어 지니까 규칙을 만든게 실제로 사용하는 이진 트리야.
왼쪽 다음 노드는 자기보다 작은 수, 오른쪽 다음 노드는 자기보다 큰 수를 갖는 노드를 배치하는 규칙을 넣어서
탐색을 빨리 할 수 있도록 한거지.
구백육
구백육
뉘일
커흑 감사합니다