트리

트리는 n(n>=1)개의 유한 노드로 차원 관계를 가진 집합을 구성한다.그것은 다음과 같은 특징을 가지고 있다. 각 노드는 0개 또는 여러 개의 하위 노드가 있다.부모 노드가 없는 노드를 루트 노드라고 부른다.모든 비뿌리 노드는 부모 노드가 있고 하나밖에 없다.루트 노드를 제외하고 모든 하위 노드는 교차하지 않는 여러 개의 하위 나무로 나눌 수 있다.
두 갈래 나무는 노드마다 최대 두 그루의 나무가 있는 나무 구조다.보통 자목은'좌자수'와'우자수'라고 불린다.두 갈래 나무는 두 갈래 찾기 나무와 두 갈래 더미를 실현하는 데 자주 쓰인다.두 갈래 나무의 관련 성질: 두 갈래 나무의 매 결점은 기껏해야 두 그루의 나무(2보다 큰 결점은 존재하지 않는다), 두 갈래 나무의 자나무는 좌우의 구분이 있기 때문에 순서가 뒤바뀌어서는 안 된다.두 갈래 나무의 i층에는 2^(i-1)개의 결점이 있다.깊이가 k인 두 갈래 나무는 기껏해야 2^k-1개의 결점이 있다.한 그루의 깊이가 k이고 2^k-1개의 노드가 있는 두 갈래 나무를 만 두 갈래 나무라고 부른다.깊이는 k이고 n개의 노드가 있는 두 갈래 나무는 모든 노드가 깊이가 k인 만 갈래 나무에 있고 번호가 1부터 n까지의 노드에 대응할 때만 완전 두 갈래 나무라고 부른다.
두 갈래 나무의 세 가지 역행 방법: 두 갈래 나무의 일부 응용에서 나무에서 특정한 특징을 가진 노드를 찾거나 나무의 모든 노드를 처리하도록 요구하는데 이것은 두 갈래 나무의 역행과 관련된다.두 갈래 나무는 주로 세 개의 기본 단원으로 구성되어 있는데 뿌리 노드, 왼쪽 나무와 오른쪽 나무이다.만약 선좌후우를 한정한다면 이 세 부분의 역행 순서에 따라 선차역행, 중차역행과 후속역행 세 가지로 나눌 수 있다.
(1) 두 갈래 나무가 비어 있으면 비어 있다. 그렇지 않으면 뿌리 노드에 접근하고 왼쪽 나무를 먼저 훑어보고 오른쪽 나무를 먼저 훑어본다.(2) 두 갈래 나무가 비어 있으면 비어 있다. 그렇지 않으면 왼쪽 나무를 중순으로 훑어보고 뿌리 노드를 방문하고 마지막으로 오른쪽 나무를 중순으로 훑어본다.(3) 두 갈래 나무가 비어 있으면 빈 동작을 한다. 그렇지 않으면 앞뒤로 왼쪽 트리를 훑어보고 뿌리 노드를 방문하고, 그 다음에 오른쪽 트리를 훑어보고 마지막으로 뿌리 노드를 방문한다.
두 갈래 찾기 트리는 두 갈래 정렬 트리로 두 갈래 검색 트리라고도 부른다.두 갈래는 나무나 빈 나무 또는 다음과 같은 성질을 가진 두 갈래 나무를 찾는다. (1) 왼쪽 나무가 비어 있지 않으면 왼쪽 나무의 모든 결점의 값이 뿌리 결점의 값보다 작다.(2) 오른쪽 트리가 비어 있지 않으면 오른쪽 트리의 모든 결점의 값이 뿌리 결점의 값보다 크다.(3) 왼쪽, 오른쪽 나무도 각각 두 갈래 정렬 나무이다.(4) 키 값이 같은 결점이 없다.
n개의 노드를 포함하는 두 갈래 찾기 트리의 평균 찾기 길이는 나무의 형태와 관계가 있다.최악의 경우 선후로 삽입된 키워드가 질서정연할 때 구성된 두 갈래 찾기 트리는 단일 트리로 탈바꿈하고 나무의 깊이는 n으로 그 평균 찾기 길이(n+1)/2(순서 찾기와 동일), 가장 좋은 상황은 두 갈래 찾기 트리의 형태와 반절절 찾기 판정 트리가 같고 그 평균 찾기 길이는log2(n)와 정비례한다.평균 상황에서 두 갈래 찾기 트리의 평균 찾기 길이와logn은 같은 수량급이기 때문에 더 좋은 성능을 얻기 위해 보통 두 갈래 찾기 트리의 구축 과정은'균형화 처리'를 해야 한다. 이후에 우리는 균형 두 갈래 트리와 붉은색 검은 나무를 소개할 것이다. 이런 것들은 모두 찾기 트리의 높이를 O(log(n)로 할 수 있다.

// 
class TreeNode {
  E element;
  TreeNode left;
  TreeNode right;

  public TreeNode(E e) {
    element = e;
  }
}

두 갈래 찾기 트리의 세 가지 반복은 모두 직접 귀속적인 방법으로 실현할 수 있다.

// 
protected void preorder(TreeNode root) {

  if (root == null)
    return;

  System.out.println(root.element + " ");
  preorder(root.left);
  preorder(root.right);
}

// 
protected void inorder(TreeNode root) {

  if (root == null)
    return;

  inorder(root.left);
  System.out.println(root.element + " ");
  inorder(root.right);
}

// 
protected void postorder(TreeNode root) {

  if(root == null)
    return;

  postorder(root.left);
  postorder(root.right);
  System.out.println(root.element + " ");
}

두 갈래 찾기 트리의 간단한 구현:

public class BST> {
  private TreeNode root;
  //  
  public BST() {
  }

  //  
  public boolean search(E e) {
    TreeNode current = root;
    while (current != null) {
      if (e.compareTo(current.element) < 0) {
        current = current.left;
       }
      else if (e.compareTo(current.element) > 0) {
        current = current.right;
      }
      else {
        return true;
      }
    }
    return false;
  }

  //  
public boolean insert(E e) {
  if (root == null) {
    root = creatNewNode(e);
  }
  else {
    TreeNode parent = null;
    TreeNode current = root;
    while (current != null) {
      if (e.compareTo(current.element) < 0) {
        parent = current;
        current = current.left;
      }
      else if (e.compareTo(current.element) > 0) {
        parent = current;
        current = current.right;
      }
      else {
        return false;
      }
    }

    // 
    if (e.compareTo(parent.element) < 0) {
      parent.left = creatNewNode(e);
    }
    else {
      parent.right = creatNewNode(e);
    }
  }
  return true;
}

  //  
  protected TreeNode creatNewNode(E e) {
    return new TreeNode(e);
  }
}

//  
class TreeNode> {
  E element;
  TreeNode left;
  TreeNode right;
  public TreeNode(E e) {
    element = e;
  }
}

균형 두 갈래 나무는 AVL 나무라고도 부른다. 그것은 빈 나무이거나 다음과 같은 성질을 가진 두 갈래 나무이다. 그의 왼쪽 나무와 오른쪽 나무는 모두 균형 두 갈래 나무이고 왼쪽 나무와 오른쪽 나무의 깊이 차이의 절대치는 1을 넘지 않는다.AVL 트리는 가장 먼저 발명된 자평형 두 갈래 찾기 트리 알고리즘이다.AVL의 모든 노드에 있는 두 아들 나무의 높이의 최대 차이는 1이기 때문에 고도 균형 나무라고도 부른다. n개의 결점의 AVL 나무의 최대 깊이는 약 1.44log2n이다.찾기, 삽입, 삭제는 평균과 최악의 경우 모두 O(logn)입니다.추가와 삭제는 트리를 한 번 또는 여러 번 회전해서 다시 균형을 잡아야 할 수도 있습니다.빨간색과 검은색 나무는 균형 두 갈래 나무의 일종으로 최악의 상황에서 기본적인 동적 집합 조작의 사건 복잡도를 O (logn) 로 보장한다.붉은색 나무와 균형 두 갈래 나무의 차이는 다음과 같다. (1) 붉은색 나무는 완전한 균형을 추구하는 것을 포기하고 대체적인 균형을 추구한다. 균형 두 갈래 나무의 시간 복잡도와 차이가 크지 않은 상황에서 매번 삽입할 때마다 최대 세 번의 회전만 하면 균형을 이룰 수 있고 실현하는 것도 더욱 간단하다.(2) 밸런스 트리는 절대 밸런스를 추구하고 조건이 까다로우며 실현하기가 번거로우며 매번 새 노드를 삽입한 후 회전해야 하는 횟수는 예측할 수 없다.