랜덤 액세스로 자체 정렬 된 데이터 구조

Question

랜덤 액세스로 자체 정렬 된 데이터 구조를 구현해야합니다. 어떤 아이디어?

Answer 1

자기 정렬은 다소 모호합니다. 무엇보다도 먼저

어떤 종류의 데이터 구조입니까?

서로 다른 데이터 구조의 많은 등, 거기에 있습니다

• 링크 된 목록
• 이중 연결리스트
• 이진 트리
• 해시 세트 /지도
• 스택
• 힙

많은 사람들은 다른 사람들과 다르게 행동하고 물론 그들의 장점을 가지고 있습니다.

이제는 스택과 같이 모두 자체 정렬 할 수 없거나 그렇게해야하는 것은 아닙니다. 셀프 정렬하는 것이 이상 할 것입니다.

그러나 연결된 목록과 이진 트리는 자체 정렬 일 수 있으며이를 위해 다른 방법으로 다른 시간에 정렬 할 수 있습니다. 링크 된 목록

를 들어

나는 이것에 대한 Insertion sort을 preffere 것입니다, 당신은 위키 및 기타 장소에서 모두 이것에 대해 여러 가지 좋은 기사를 읽을 수 있습니다. 나는 붙여 넣기 된 링크를 좋아한다. 그것을보고 개념을 이해하려고 노력하십시오.

당신이 그것을 삽입 한 후 정렬 할 경우

는, 즉 임의의 시간에, 그럼 당신은 단지 일종의 어쩌면, bubblesort 아니면 quicksort, 그래도 난 거품 정렬을 피할 것 삽입보다는 algororithm 다른 정렬을 구현할 수 있습니다, 그것은 훨씬 느리다! 그러나 마음을 헐떡 거리기 쉽습니다.

랜덤 액세스

랜덤 항상 뭔가 이잖아 그래서 주변에 나와은 "getAt을"좋은 무작위을 수행하는 당신은 당신이 연결 목록이있는 경우, 당신의 방법에하고있을 것이다 방법에 대한 읽기가되고 -method를 사용하면 0에서 n 사이의 인덱스를 무작위로 추출하여 해당 인덱스에서 항목을 가져올 수 있습니다.

Answer 2

정렬 된 목록을 유지 관리하고 임의적으로 액세스하려면 적어도 O (lgN)/작업이 필요합니다. 따라서 AVL, red-black trees, treaps 또는 기타 유사한 데이터 구조를 찾아 무작위 색인 생성을 지원하도록 강화하십시오. 이해하기 쉽고 구현하기 쉽기 때문에 treaps을 제안합니다.

treap 트리를 풍부하게하는 한 가지 방법은 각 노드에 해당 노드를 루트로하는 하위 트리의 노드 수를 유지하는 것입니다. 트리를 수정할 때 개수를 업데이트해야합니다 (예 : 삽입/삭제).

Answer 3

저는 최근에 데이터 구조 구현에 너무 관여하지 않았습니다. 아마이 대답은 전혀 대답이 아닙니다 ... Thomas Cormen이 쓴 "Introduction to algorithms"을보아야합니다.이 책에는 많은 데이터 구조의 내부 동작에 대한 설명과 함께 많은 "조리법"이 있습니다. 반면에 알고리즘 작성에 소요되는 시간, 입력 크기 및 특수한 종류의 데이터 구조가 실제로 필요한지 여부를 고려해야합니다.

Answer 4

자체 정렬 된 데이터 구조는 2 진 검색 트리가 될 수 있습니다. 당신은 자기 정렬 된 데이터 구조와 자기 균형을 원한다면. AVL 트리를 사용할 수 있습니다. 랜덤 액세스의 경우 검색 시간은 O (lgn)입니다.