우리는 어떻게 균형 잡힌 두 갈래 나무를 얻을 수 있습니까?

두 갈래 나무

말 그대로 binary tree란 각 노드가 최대 두 개의 자노드가 있는 모든 것을 가리킨다tree.두 갈래 나무는 비어 있을 수 있는데, 이것은 나무에 노드가 없다는 것을 의미한다.binary trees 가장 멋있는 점은 귀환 구조다.이것은 규칙을 모든 하위 트리에 순서대로 적용함으로써 전체 트리에 적용할 수 있다는 것을 의미한다.

두 갈래 나무를 정의하기 위해서는 두 가지 데이터 구조가 필요하다.하나는 뿌리 노드의 전체 두 갈래 나무 구조를 추적하는 것이다.다른 하나는 좌우 트리의 노드 구조를 추적하는 것이다.

class binaryTree {
  public:
    node * root; //a pointer to the root
};

현재, 우리는 노드 구조를 정의합니다. 이것은 왼쪽과 오른쪽 하위 노드를 추적하고 데이터를 포함합니다. 이 예에서 우리는 키라고 합니다.

class node {
  public:
    node * left; //a pointer to the root of the left subtree
    node * right; //a pointer to the root of the right subtree
    int key;
};

여기서 우리는 관건적인 데이터 유형integer을 가정하는데 단지 간단하게 보기 위해서이다.그러나 key 유형은 비교 연산자를 허용하는 모든 데이터 구조일 수 있습니다. 즉, <,>,>=,<=,=.
이 과정은 https://algodaily.com에 처음 발표되었고 저는 그곳에서 기술 면접 과정을 개설했고 웅대한 개발자를 위해 사고문을 썼습니다.

이진 검색 트리

두 갈래 검색 트리(약칭 orBST는 두 갈래 트리의 특례로 트리의 키 값의 배치에 추가적인 제약이 있다.매우 간단합니다. BST는 다음과 같은 규칙으로 정의됩니다.

왼쪽 트리의 모든 노드의 키 값이 부모 노드의 키 값보다 작거나 같음

오른쪽 하위 트리의 모든 노드의 키 값이 부모 노드의 키 값보다 크거나 같음

다음 그림은 바이너리 검색 트리의 예를 보여 줍니다.

균형 BST

Abalanced BST는 BST의 일종으로 그 중에서 좌우 자목의 높이 차이는 11을 넘지 않는다.이 예시도들은 반드시 이 점을 명확하게 설명해야 한다.

BST 밸런싱 방법

BST에는 red black trees 또는 AVL trees 등의 균형 알고리즘이 있습니다.이러한 구조에서는 BST에 키를 삽입하고 삭제하여 트리의 균형을 유지합니다.
그러나 unbalanced 나무 한 그루를 정할 때 어떻게 효율적으로 균형 나무로 전환합니까?매우 간단하고 효과적인 알고리즘은 수조를 사용하여 실현할 수 있다.다음 두 단계를 수행합니다.

BST를 순서대로 훑어보고 값을 그룹에 저장합니다.그룹 값은 오름차순으로 정렬됩니다.

정렬된 배열에서 균형 잡힌 BST 트리를 생성합니다.

지금까지 우리의 계획은 두 가지 절차가 있었다.
1단계: 순차 반복
단계 2: 균형 잡힌 BST 만들기
탐색해 봅시다.균형 BST를 효과적으로 만드는 위조 코드는 다음과 같이 기본 및 귀속 상태를 반복합니다.

기본 사항:

그룹 크기가 0이면 null 포인터를 반환하고 중지합니다.

귀속 상황:

정의build 방법.

수조의 중간 부분을 가져와 뿌리 노드로 만든다.

호출 수조의 왼쪽 부분의 귀속 용례build.루트 노드의 왼쪽 하위 노드는 이 귀속 호출이 되돌아오는 지침입니다.

수조의 오른쪽 부분을 호출하는 귀속 용례build.루트 노드의 오른쪽 하위 노드는 이 귀속 호출이 되돌아오는 지침입니다.

단계 1에서 생성된 루트 노드를 가리키는 포인터를 반환합니다.

위의 위조 코드가 우아한 이유는 나무 자체가 귀속되기 때문이다.따라서 우리는 그것에 대해 귀속 과정을 응용할 수 있다.우리는 같은 물건을 왼쪽 나무와 오른쪽 나무에 한 번 또 한 번 응용했다.
패턴의 중간 위치를 구하는 방법을 알고 싶을 수도 있습니다.단순 공식(size/2)은 중간 항목의 색인을 되돌려줍니다.물론 이 가설 그룹의 인덱스는 0 부터 시작한다.
앞의 위조 코드가 어떻게 작동하는지 예시를 봅시다.우리는 간단한 장면을 채택한 후에 더욱 복잡한 장면을 구축할 것이다.

어레이: [30]

우선, 우리는 다음과 같은 원소만 있는 수조(즉 30를 살펴보자.

어레이: [31, 37, 38]

이제 크기가 3인 그룹을 봅시다.

어레이: [10, 11]

지금 우리는 두 원소의 짝수 크기를 가진 수조를 보았다.

어레이: [10, 11, 17, 19]

현재, 우리는 예시를 네 개의 원소를 가진 짝수 크기의 수조로 확장할 수 있다.

어레이: [10, 11, 17, 19, 30, 31, 37, 38]

여덟 개의 원소의 크기가 균일한 수조를 가지고 있다.

기왕 우리가 균형이 어떻게 작동하는지 알게 된 이상, 우리는 재미있는 부분을 할 수 있다. 그것이 바로 인코딩이다.이것은 C++ 조수 함수입니다. 이것은 우리가 이전에 정의한 귀속 루틴 build 입니다.
다음 코드는 상기 helper 귀속 함수build를 호출하는 방법을 보여 줍니다.

void build(int *arr, int size, binaryTree &tree) {
    tree.root = build(arr, 0, size-1);
}

// build returns a pointer to the root node of the sub-tree
// lower is the lower index of the array
// upper is the upper index of the array
node * build(int * arr, int lower, int upper) {
  int size = upper - lower + 1;
  // cout << size; //uncomment in case you want to see how it's working
  // base case: array of size zero
  if (size <= 0)
    return NULL;
  // recursive case
  int middle = size / 2 + lower;
  // make sure you add the offset of lower
  //  cout << arr[middle] << " "; //uncomment in case you want to see how it's working
  node * subtreeRoot = new node;
  subtreeRoot - > key = arr[middle];
  subtreeRoot - > left = build(arr, lower, middle - 1);
  subtreeRoot - > right = build(arr, middle + 1, upper);
  return subtreeRoot;
}

상술한 코드를 시험적으로 사용하기 전에 앉아서 종이와 펜으로 몇 번 코드를 시험적으로 운행해서 그것이 어떻게 작동하는지 보는 것이 가장 좋다.앞의 코드의 복잡도는 O(N) 이고, 그 중에서 N 은 나무의 키 수입니다.Inorder traversal소요O(N)시간.패턴의 각 요소에 한 번만 액세스하기 때문에 build 방법의 시간 복잡도 O(N) 입니다.
이 과정은 https://algodaily.com에 처음 발표되었고 저는 그곳에서 기술 면접 과정을 개설했고 웅대한 개발자를 위해 사고문을 썼습니다.