[은나현] 5장 자료구조

[1000hyehyang]

질문을 달아주세요

[TaeHoon96]

자료구조에서 시간 복잡도가 같은 경우에도 해시 테이블보다 트리를 사용하는 경우가 있다면, 그 이유는 무엇인가요?

[nan0silver]

해시 테이블은 평균적으로 O(1)의 성능을 제공하지만, 키의 정렬이 불가능하고 순회 시 순서가 보장되지 않습니다.
반면 트리는 O(log n)의 성능이지만 키가 항상 정렬된 상태로 유지되기 때문에 범위 검색이나 정렬된 순서로 순회해야 할 경우에는 트리 구조가 더 적합합니다.
또한 트리는 해시 충돌이나 해시 함수 품질에 영향을 받지 않기 때문에 안정적인 성능이 필요한 상황에서도 선택될 수 있습니다.

[songcw8]

그래프와 트리의 차이점은 무엇인가요?

[nan0silver]

그래프는 정점과 간선이 이루어진 일반적인 자료구조로, 정점 간의 연결 방향이나 사이클 유무에 제한이 없습니다.
반면, 트리는 그래프의 일종이지만, 사이클이 없고 모든 노드가 단 하나의 부모만 가지는 계층적 구조입니다.
즉, 트리는 방향이 있는 비순환 그래프이며, 루트부터 자식 노드로이 계층적 관계를 명확히 표현할 수 있습니다.
그래프는 지하철 노선도나 소셜 네트워크처럼 복잡한 관계 표현에, 트리는 디렉터리 구조나 이진 탐색 트리처럼 계층적 구조 표현에 적합합니다.

[1000hyehyang]

이진 탐색 트리는 어떤 문제점이 있고 이를 해결하기 위한 트리 중 한 가지를 설명해보세요.

[nan0silver]

이진탐색트리는 평균적으로 O(logn)의 탐색 성능을 제공하지만, 데이터가 정렬된 순서로 삽입되면 한쪽으로 치우친 "편향 트리"가 되어 성능이 O(n)까지 저하될 수 있는 단점이 있습니다.
이 문제를 해결하기 위한 대표적인 트리 구조 중 하나가 AVL 트리입니다.
AVL 트리는 삽입이나 삭제 시마다 각 노드의 높이 차이를 계산해 균형을 맞추는 "자기 균형 이진 탐색 트리"로, 항상 O(logn)의 시간 복잡도를 유지할 수 있도록 회전 연산을 수행합니다.

[jungmyung16]

해시 테이블과 시간 복잡도에 대해 설명해주세요.

[nan0silver]

해시 테이블은 키를 해시 함수에 넣어 해시값을 계산하고, 이를 배열의 인덱스로 사용해 데이터를 저장하는 자료구조입니다.
이 구조 덕분에 평균적으로 삽입, 삭제, 검색 모두 O(1)의 시간 복잡도를 갖는 것이 가장 큰 장점입니다
하지만 해시 충돌이 발생할 경우, 체이닝이나 오픈 어드레싱으로 처리하게 되어 최악의 경우 시간 복잡도가 O(n)까지도 늘어날 수 있습니다.
그래서 좋은 해시 함수와 적절한 해시 테이블 크기 관리가 중요합니다.