트리
정의
자녀의 자녀가 부모 노드에 연결되면, 그것은 다시 자녀 노드에 연결된 여러 자녀 노드가 있는 데이터 구조의 재귀 형태이지만 일반적으로 트리로 인식되지 않습니다. 트리는 몇 가지 기본적이고 흥미로운 특성을 가지고 있지만 트리 구조에서 일부 노드를 취하면 이러한 생성된 연결되지 않은 트리의 수는 해당 노드에 연결된 가장자리 수와 동일합니다.
자식 노드에서 부모로 계속 올라가면 결국 부모없이 하나의 노드로 이어집니다. 이 노드는 루트 노드라고 불리며 루트 노드 주위에 줄 지어있는 그림은 트리의 구조와 유사하며 때로는 인테이트라고도하는 트리라고합니다.
뿌리가 없는 나무를 정의하지 않는 나무로 뿌리를 뽑자.
뿌리가 있는 나무에서는 다른 용어가 정의됩니다. 높이는 뿌리의 높이를 0으로 정의하고 아이의 높이는 원래 노드보다 큰 것으로 정의됩니다. 마지막으로 노드의 정의는 아이가 없는 노드입니다. 라우팅 트리에서 엔드 노드를 1도 노드로 정의합니다.
이진 트리
가장 간단한 형태의 나무는 부모 노드 아래에 두 명의 자녀 만 있으며, 두 명의 자녀는 왼쪽과 오른쪽 자녀로 나뉘며, 두 개의 포인트 포인터는 각각 하나의 값, 왼쪽 및 오른쪽을 가리키는 것입니다.
일반적으로 n-child를 가질 수있는 트리 구조에서, 원래의 자식 노드는 하나 이상의 각 자식에 하나의 노드를 추가하고 오른쪽에 형제 노드 (좌우, 우측)가 추가되어 2 진 트리 구조로 변환 될 수 있습니다. 따라서 모든 나무는 이진 트리 형식으로 재구성 될 수 있습니다 (같은 것이 사실입니다). 따라서 나무는 특별한 이유없이 이진 트리에서 구현됩니다.
이진 탐색 트리
이진 트리의한 유형인 노드의 왼쪽 분기는 노드의 값보다 작은 값만 가지고 있었고 오른쪽 분기는 큰 값으로만 구성되었습니다. 또한, 노드의 좌식 분기는 좌식 값보다 작은 값만 가지고 있으며, 좌식 분기는 좌식 값보다 큰 값만 가지고 있으며, 이진 탐색 트리의 어느 쪽이 이진 탐색 트리를 가지고 있는지에 관계없이 동일한 규칙으로 정렬된 우측 분기가 있습니다. 같은 방식으로 배열됩니다.
이러한 방식으로 구성되면 일부 값 n을 찾을 때 루트 노드에 비해 n이 작으면 루트 노드보다 큰 값으로 모인 오른쪽으로 항해할 필요가 없습니다. 마찬가지로, n이 루트 노드의 왼쪽 자식보다 크면 왼쪽 자식을 탐색할 필요가 없습니다. 즉, 트리 자체는 이진 탐색에 적합한 구성입니다. 값을 찾을뿐만 아니라 값을 삽입하거나 삭제할 때 동일한 과정을 거치기 때문에 이상적인 상황에서 검색 / 삽입 / 삭제는 모두 시간 복잡성 O (log N)를가집니다.
단점은 값이 삽입되거나 삭제되면 운이 좋다면 O (N)가 최악의 경우 시간이 걸립니다.예를 들어, 빈 이진 항법 트리에 1에서 100 순서로 삽입하면 첫 번째 루트 노드는 1보다 크고 3은 1보다 커서 1의 오른쪽 아이가 되어 1의 오른쪽, 2의 오른쪽입니다.이 방식으로 트리의 오른쪽 끝으로 계속 자랍니다. 50을 찾아서이 상태로, 결국에는 더 이상 선형 항법 또는 다른 것이 1에서 오른쪽으로 내려 가지 않고 나무가 원래대로 되었다고합니다. 어떤 경우에는 비켜가세요.
스레드 이진 트리
왼쪽 또는 오른쪽 자식 노드가 없는 노드의 링크를 중간 탐색에서 리드 노드 또는 후속 노드에 연결하는 이진 트리입니다. 현재 링크가 자식 노드인지 또는 선행 노드인지 또는 후속 노드인지 여부를 나타내는 플래그가 자식 노드에 대한 링크에 추가됩니다.반복 호출이나 스택을 사용하지 않고도 중위 검색을 구현할 수 있으며, 연속 검색 속도가 빨라집니다. 삽입 / 삭제시 링크를 다시 연결하는 프로세스가 필요하기 때문에 일반적인 이진 트리보다 구현이 더 복잡합니다.