특정 노드의 자식 노드 중에서 단말 노드(자식 노드가 없는 노드) 만 찾아 내고 싶어요
이런 동작을 하는 알고리즘이나 탐색 트리 가 있으면 참고 하고 싶은데 혹시 그런게 있을까요?
[질문] 이거 구현 조언좀여... (트리 구조체)
익명(122.38)
2021-12-31 22:56
추천 0
댓글 34
다른 게시글
-
(대충 똥글) [3][%] Ashtray(dnstjdwjs) | 21.12.31추천 0
-
zappa로 장고 배포해본사람 있냐 [3][%] 익명(121.159) | 21.12.31추천 0
-
다들 새해 목표 말해보자 [25][질문] Sayori(arwen02) | 21.12.31추천 2
-
c# 어느정도 정확하게 20ms 대기하는 방법이 있을까요? [24][질문] 익명(106.101) | 21.12.31추천 0
-
여기 앱개발자들있음?? [16][⚠애니짤] 익명(113.10) | 21.12.31추천 1
-
연말에 기획이랑 대판 싸웠다 [23][%] 익명(221.154) | 21.12.31추천 43
-
문자열의 동적배열 질문 [17][질문] 익명(122.38) | 21.12.31추천 0
-
멀쩡히 있는 글은 박제 왜 함 [4][%] 감성매매법(shoheitakagi) | 21.12.31추천 3
-
책샀다 [9][%] Sayori(arwen02) | 21.12.31추천 1
-
왜 프로그래밍을 취미로 하게 됐지[%] Sayori(arwen02) | 21.12.31추천 0
그냥 자식 노드가 null인 거만 찾으면 되잖아
모든 자식노드들을 찾아 내려가서요?
당연하지 - dc App
그건 좀 느릴거 같아서요 좀더 빠르고 최적화된 방법은 없을까요?
ㅇㅇ
트리 자체도 충분히 빠른데 뭘 - dc App
모든 노드에서 찾아야 해서요 중복되는 것들도 있을텐데 아까워서요
포인터 2번 타는게 전부 아님? 매번 확인해야 되는게 싫으면 null인 노드 목록을 또 들고있어야될텐데
노드 목록을 들고 잇는 방식은 어떻게 하는 거에요?
노드 추가,삭제 프로세스 끝날 때 leaf node가 parent에 업데이트 해주거나? 뭔가 연쇄적으로 갱신될듯한데 요지는 탐색단계에서 시간을 줄이려면 구축단계에서 미리 처리하고 공간을 더 쓰는게 당연하지 않을까
나도 알고리즘 고자라 잘은 모르지만 결국 DB 인덱싱해서 insert느려지고 select 빨라지는거랑 동일한거 아니냐
해당 노드의 자식 노드인지 아닌지 구별하는데에는 어떤 방식이 좋을까요?
조언 감사해요 참고해 볼게요
그럼 자료구조와 알고리즘은 복잡도에 비해 성능은 공짜 수준이라고 생각한거임?
해당 댓글은 삭제되었습니다.
모든 노드마다 1번씩 확인하면서 자식 노드로 내려가야 하구요, 개수는 정해 져 있지 않고, 단말노드에 자식노드가 추가 될수는 있지만 이외에 변동사항은 발생하지 않아요
단말노드에 자식노드가 추가 될지 말지는 모든 노드에서 자기가 가지고 잇는 값을 통해 계산된 결과에 달려잇어요
트리의 모든 노드는 class구요, 단말노드를 포함해 모든 노드에서 문자를 가지고 있는데요 특정 문자일때는 찾아낸 모든노드에 2개의 자식노드를 추가 하고요 e다른 특정 문자 일때는 찾아낸 모든 노드에 1개의 자식노드를 추가하고요 또 특정문자가 없으면 찾아낸 노드에 자식 노드를 추가 하지 않아요 추가된 자식 노드 또한 같은 방식으로 자기자신 혹은 (자식노드가 있다면) 찾아낸 모든 노드에 같은 방식으로 자식 노드를 추가해요
특정 문자는 2가지만 있어요
계산 부분은 뺴도 될거 같아서 설명에서 제외했어요
그냥 간단한 문제잖아... 느리면 쓰지 말아야지... 트리가 편리하다면 느려도 써야지. 따지고 보면 직접 메모리 접근이랑 트리랑 거치는 단계가 수십배정도 차이날텐데 성능 때문에 배열만 쓴다면 그거 가지고 할 수 있는게 머있는데?
트리를 쓰면 편리한대신 느려지는건 맞는데 트리를 사용해야 하고 제가 생각못한 좋은 방법이 잇을까해서요
느려봤자 얼마나 느리다고... 컴퓨터가 존나 빠르잖아 그냥 느릴거 같아서 찾는거임? 실제로 느림?
하려는 동작 한번당 모든 노드에서 확인해야 하는데 이 동작이 여러번 수행되는데다가 오래된 구형에서도 원활이 동작 했으면 해서요
ㄴ 임베디드냐?
최신컴이나 대부분의 경우 임베디드도 아니고 생각할 필요 없는건 맞아요 근데 인터넷 하나 키는데도 오래걸리는 조선컴 같은데서도 돌아 갔으면 해서요
위에 설명 보고 궁금한 점이 있는데 그럼 같은 문자를 여러 번 넣을 떄는 무시하는 건가?
조금만더 자세히 이야기 해주실수 있나요 같은 문자를 여러번 넣는다는건 어떤 노드에서 가지고 잇는 문자와 그 노드의 자식노드가 가지고 있는 문자가 같을때 말씀하시는건가요?
이미 한 노드가 자식 노드 두 개를 가지고 있고 모든 노드에 2개의 자식 노드를 추가한다면 그 노드는 [ [a, b], [c, d], [ ], [ ] ] 이렇게 되는 건가? 모든 노드에 저장되어있는 문자는 노드를 추가할 때 아무 영향을 주지 않는 거지?
모든 노드가 아니라 찾아낸 모든노드(자식 노드들 중에서 단말노드만)에 문자에 따라 1개 혹은 2개의 자식노드를 추가하거나, 문자가 없는경우 추가하지 않아요. 그외의 상호 작용은 설명도 복잡해지고 제가 조정할수 있어서 생략 했어요
그러니까 해당 노드에서 자식노드를 따라가서 도달할수 잇는 단말 노드에 한해 자식 노드를 추가하는거에요
그럼 차라리 hash table을 사용해서 단말 노드를 관리해. 추가할 때 iterate 해서 전부 추가한 뒤 기존에 있던 노드들은 제거하고 새로 추가된 건 넣어
조언 감사해요
그렇게 단말노드 빨리 찾고싶으면 링크드리스트 단말노드 컨테이너 만들어서 관리하든지 다만 트리에 넣고 뺄때 추가작업 해줘야지 ,