LinkedList와 이진 검색 트리의 차이점

https://stackoverflow.com/questions/270080

06-07-2019
|

문제

Linked List와 BinarySearchTree의 주요 차이점은 무엇입니까?BST는 단지 LinkedList를 유지하는 방법입니까?내 강사는 LinkedList와 BST에 대해 이야기했지만 비교하지 않았거나 언제 다른 것보다 선호하는지 말하지 않았습니다.이것은 아마도 바보 같은 질문이지만 정말 혼란 스럽습니다.누군가가 이것을 간단한 방법으로 명확하게 설명할 수 있다면 감사하겠습니다.

해결책

링크 된 목록 :

Item(1) -> Item(2) -> Item(3) -> Item(4) -> Item(5) -> Item(6) -> Item(7)

이진 트리 :

                 Node(1)
                /
            Node(2)
           /    \
          /      Node(3)
  RootNode(4)
          \      Node(5)
           \    /
            Node(6)
                \
                 Node(7)

링크 된 목록에서 항목은 단일 다음 포인터를 통해 함께 연결됩니다. 이진 트리에서 각 노드는 0, 1 또는 2 서브 노드를 가질 수 있습니다. (이진 검색 트리의 경우) 왼쪽 노드의 키는 노드의 키보다 작고 오른쪽 노드의 키는 그 이상입니다. 노드. 트리가 균형을 이루는 한 각 항목에 대한 검색 경로는 링크 된 목록의 것보다 훨씬 짧습니다.

SearchPaths :

------ ------ ------
key    List   Tree
------ ------ ------
1      1      3
2      2      2
3      3      3
4      4      1
5      5      3
6      6      2
7      7      3
------ ------ ------
avg    4      2.43
------ ------ ------

더 큰 구조에 의해 평균 검색 경로가 더 작아집니다.

------ ------ ------
items  List   Tree
------ ------ ------
     1      1   1
     3      2   1.67
     7      4   2.43
    15      8   3.29
    31     16   4.16
    63     32   5.09
------ ------ ------

다른 팁

ㅏ 이진 검색 트리 각 내부 노드가있는 이진 트리입니다 엑스 왼쪽 하위 트리에 저장된 요소를 저장합니다. 엑스 보다 적거나 같다 엑스 및 오른쪽 하위 트리에 저장된 요소 엑스 보다 크거나 동일합니다 엑스.

이제 a 링크 된 목록 각각 임의의 값과 다음 및/또는 이전 노드를 가리키는 하나 또는 두 개의 참조를 포함하는 일련의 노드로 구성됩니다.

컴퓨터 과학에서 a 이진 검색 트리 (BST) 이진 트리 데이터 구조는 다음 속성을 갖습니다.

각 노드 (트리의 항목)는 뚜렷한 값을 갖습니다.
왼쪽 및 오른쪽 하위 트리는 모두 이진 검색 트리 여야합니다.
노드의 왼쪽 하위 트리에는 노드 값보다 적은 값 만 포함됩니다.
노드의 오른쪽 하위 트리에는 노드 값보다 큰 값 만 포함됩니다.

컴퓨터 과학에서 a 링크 된 목록 기본 데이터 구조 중 하나이며 다른 데이터 구조를 구현하는 데 사용할 수 있습니다.

따라서 바이너리 검색 트리는 링크 된 목록 또는 배열로 구현 될 수있는 추상 개념입니다. 링크 된 목록은 기본 데이터 구조입니다.

주요 차이점은 이진 검색 트리가 정렬된다는 것입니다. 이진 검색 트리에 삽입하면 해당 요소가 메모리에 저장되는 것은 해당 값의 함수입니다. 링크 된 목록을 사용하면 요소가 값에 관계없이 목록에 맹목적으로 추가됩니다.

바로 일부 트레이드 오프 할 수 있습니다 : 연결된 목록 보존 삽입 순서와 삽입이 저렴합니다. 이진 검색 트리는 일반적으로 검색이 더 빠릅니다.

링크 된 목록은 서로 연결된 순차적 수의 "노드"입니다.

public class LinkedListNode
{
     Object Data;
     LinkedListNode NextNode;
}

이진 검색 트리는 유사한 노드 구조를 사용하지만 다음 노드에 연결하는 대신 두 하위 노드에 연결됩니다.

public class BSTNode
{
    Object Data
    BSTNode LeftNode;
    BSTNode RightNode;
}

BST에 새 노드를 추가 할 때 특정 규칙을 따르면 트래버스에 매우 빠른 데이터 구조를 만들 수 있습니다. 여기서 다른 답변은 이러한 규칙을 자세히 설명했습니다. 코드 수준에서 노드 클래스의 차이점을 보여주고 싶었습니다.

정렬 된 데이터를 BST에 삽입하면 링크 된 목록으로 끝나고 트리 사용의 이점이 상실된다는 점에 유의해야합니다.

이로 인해 링크 사전 목록은 O (N) 트래버스 데이터 구조이며, BST는 최악의 경우 O (N) 트래버스 데이터 구조이고 최상의 경우 A (log N)입니다.

연결된 목록과 BST는 둘 다 컨테이너 역할을 하는 데이터 구조라는 점을 제외하면 실제로 공통점이 많지 않습니다. 연결리스트 기본적으로 목록의 순서를 유지하면서 목록의 어느 위치에서나 요소를 효율적으로 삽입하고 제거할 수 있습니다.이 목록은 한 요소에서 다음 요소(종종 이전 요소)까지의 포인터를 사용하여 구현됩니다.

ㅏ 이진 검색 트리 반면에 더 높은 추상화의 데이터 구조(예:그것은 지정되지 않았습니다 어떻게 이는 내부적으로 구현되어 효율적인 검색이 가능합니다(예:특정 요소를 찾기 위해 모든 요소를 볼 필요는 없습니다.

연결된 목록은 퇴화된 이진 트리로 생각할 수 있습니다.모든 노드에 자식이 하나만 있는 트리입니다.

실제로 매우 간단합니다. 링크 된 목록은 특별한 순서없이 함께 묶인 많은 항목입니다. 당신은 그것을 분기하지 않는 정말 마른 나무라고 생각할 수 있습니다.

1 -> 2 -> 5 -> 3 -> 9 -> 12 -> |i. (마지막으로 끝나는 널에 대한 Ascii-Art 시도입니다)

이진 검색 트리는 두 가지 방법으로 다릅니다. 이진 부분은 각 노드가 2 어린이가 아닌 어린이 및 검색 부분은 그 어린이들이 검색 속도를 높이기 위해 배열되었음을 의미합니다.

9에는 남은 아이가없고 1, 2 및 12는 "잎"입니다. 가지가 없습니다.

이해가 되나요?

대부분의 "조회"종류의 용도의 경우 BST가 더 좋습니다. 그러나 "나중에 첫 번째-첫 번째-첫 번째 또는 최후의 첫 번째 출력을 다루는 것들의 목록을 유지하기 위해서는 링크 된 목록이 잘 작동 할 수 있습니다.

링크 된 목록의 문제는 검색 또는 삽입에 관계없이 IT 내에서 검색하는 것입니다.

단일 연결 목록의 경우 머리에서 시작하여 원하는 요소를 찾으려면 순차적으로 검색해야합니다. 전체 목록을 스캔 할 필요가 없으려면 목록 내 노드에 대한 추가 참조가 필요합니다.이 경우 더 이상 간단한 링크 목록이 아닙니다.

바이너리 트리는 본질적으로 정렬되고 탐색 가능성을 통해보다 빠른 검색 및 삽입을 허용합니다.

내가 과거에 성공적으로 사용한 대안은 건너 뛰기입니다. 이것은 링크 된 목록과 비슷하지만 추가 참조가 이진 트리와 비교할 수있는 검색 성능을 제공합니다.

링크 된 목록은 바로 ... 목록입니다. 선형입니다. 각 노드에는 다음 노드에 대한 참조가 있습니다 (이중 연결 목록에 대해 이야기하는 경우 이전의 노드). 트리 가지 --- 각 노드에는 다양한 하위 노드에 대한 참조가 있습니다. 이진 트리는 각 노드에 두 명의 자녀 만있는 특별한 경우입니다. 따라서 링크 된 목록에는 각 노드에는 이전 노드와 다음 노드가 있으며 이진 트리에는 노드에 남은 자식, 오른쪽 자식 및 부모가 있습니다.

이러한 관계는 구조를 가로 질러 이동할 수있는 방법에 따라 양방향 또는 단방향 일 수 있습니다.

유사점이 있지만 주요 차이점은 이진 검색 트리가 요소 또는 "키"에 대한 효율적인 검색을 지원하도록 설계되었다는 것입니다.

이중 연결 목록과 같은 이진 검색 트리는 구조의 다른 두 요소를 가리킵니다.그러나 구조에 요소를 추가할 때 단순히 목록 끝에 추가하는 것이 아니라 "왼쪽" 노드에 연결된 요소가 현재 노드보다 작고 "오른쪽"에 연결된 요소가 되도록 이진 트리가 재구성됩니다. 노드가 현재 노드보다 큽니다.

간단한 구현에서는 새 요소가 구조의 첫 번째 요소(트리의 루트)와 비교됩니다.그보다 작으면 "왼쪽" 분기가 선택되고, 그렇지 않으면 "오른쪽" 분기가 검사됩니다.이는 분기가 비어 있음이 발견될 때까지 각 노드에서 계속됩니다.새 요소가 해당 위치를 채웁니다.

이 간단한 접근 방식을 사용하면 요소가 순서대로 추가되면 연결 목록이 생성됩니다(성능은 동일함).노드를 재배열하여 트리의 균형을 유지하기 위한 다양한 알고리즘이 존재합니다.예를 들어, AVL 트리는 트리의 균형을 최대한 유지하여 최상의 검색 시간을 제공하기 위해 가장 많은 작업을 수행합니다.레드-블랙 트리는 트리의 균형을 유지하지 않으므로 검색 속도가 약간 느려지지만 키를 삽입하거나 제거할 때 평균 작업량이 줄어듭니다.

링크 된 목록은 서로 연결된 인접한 노드가있는 직선형 선형 데이터입니다. 당신은 그것을 직선 울타리로 간주 할 수 있습니다.

BST는 메인 트렁크가 가지에 연결된 나무와 다른 분기와 연결된 분지가있는 나무처럼 계층 적 구조입니다. 여기서 "바이너리"단어는 각 지점이 최대 2 개의 분기에 연결되어 있음을 의미합니다.

링크 된 목록을 사용하여 최대 하나의 항목에 연결된 각 항목으로 만 직선 데이터를 나타냅니다. 반면 BST를 사용하여 항목을 두 항목에 연결할 수 있습니다. BST를 사용하여 가계도와 같은 데이터를 나타낼 수 있지만 각 사람에게 두 명의 자녀가있을 수 있으므로 N-Ary 검색 트리가됩니다.

이진 검색 트리는 모든 방식으로 구현할 수 있으며 링크 된 목록을 사용할 필요가 없습니다.

링크 된 목록은 단순히 노드 내부의 다른 노드에 대한 노드 및 포인터/참조를 포함하는 구조입니다. 목록의 헤드 노드가 주어지면 링크 된 목록의 다른 노드로 탐색 할 수 있습니다. 이중 연결 목록에는 두 개의 포인터/참조가 있습니다 : 다음 노드에 대한 일반 참조뿐만 아니라 이전 노드에 대한 참조도 있습니다. 이중 연결 목록의 마지막 노드가 목록의 첫 번째 노드를 다음 노드로 참조하고 첫 번째 노드는 마지막 노드를 이전 노드로 참조하는 경우 원형 목록이라고합니다.

이진 검색 트리는 이진 검색 비교 알고리즘을 기반으로 입력을 대략적으로 두 개의 반쪽으로 나누는 트리입니다. 따라서 요소를 찾기 위해서는 거의 검색 만 있으면됩니다. 예를 들어, 1-10이있는 나무가 있고 3 개를 검색 해야하는 경우, 먼저 상단의 요소가 확인됩니다. 아마도 5 또는 6은 아마도 그보다 적을 것입니다. 그런 다음 나무가 확인됩니다. 다음 값이 3 인 경우, 그렇지 않으면 비교가 없거나 데이터가 반환 될 때까지 비교가 완료됩니다. 따라서 트리는 조회하기 위해 빠르지 만 삽입이나 삭제에는 빠르지 않습니다. 이것들은 매우 거친 설명입니다.

링크 된 목록 Wikipedia에서 이진 검색 트리, Wikipedia에서도.

그것들은 완전히 다른 데이터 구조입니다.

링크 된 목록은 각 요소가 다음 요소와 연결되는 요소와 이중 링크 된 목록의 경우 이전 요소입니다.

이진 검색 트리는 완전히 다른 것입니다. 루트 노드, 루트 노드에는 최대 두 개의 자식 노드가 있으며 각 하위 노드는 최대 두 개의 자식 음표 등을 가질 수 있습니다. 이는 매우 영리한 데이터 구조이지만 여기에서 설명하는 것은 다소 지루할 것입니다. 확인하십시오 Wikipedia Artcle 그 위에.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow