Binary Trees & Binary Search Trees(BST)

그래프란?

• 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조

트리란?

• 다음 중 아무 성질을 만족하는 무방향 그래프
• 1) 루프를 가지지 않는 연결된 그래프
• 2) N개의 노드와 N-1개의 간선으로 이루어진 연결된 그래프
• 3) 모든 두개의 노드가 나의 경로로만 연결된 그래프

Binary 트리란?

• 자식을 최대 2개만 가진 트리

Binary Search 트리란?

• Binary Tree + BST invariant
• BST invariant : 왼쪽 subTree 는 더 작은 값을, 오른쪽 subTree은 더 큰 값을 가진다.
• 중복된 값을 가지고 있다면 나의 정의에 따라 valid를 정한다. BST Operation은 중복된 값을 허용하지만 보통의 경우 중복되지 않은 원소들을 갖는 트리에 관심이 있다.

Binary Tree는 어디에 사용되는가?

• 여러 BSTs
  • 몇몇의 map과 set ADTs 구현에 사용
  • Red Black Trees
  • AVL Trees
• binary Heap 구현

Complexity of BSTs

• 평균 & 최악
• Insert O(logn) O(n)
• Delete O(logn) O(n)
• Remove O(logn) O(n)
• Search O(logn) O(n)

Adding Elements to a BST

• 모든 원소들은 comparable 해야함
• Insert 시 4가지 경우 존재 ( 항상 root에서 시작)
  • 작은 경우 Recurse down left subtree
  • 큰 경우 Recurse down right subtree
  • 같은 경우 Handling
  • null leaf인 경우 Create new node
• linear 한 경우( O(n)인 경우)
  1,2,3,4,5,6 순으로 adding 하면 직선 형태를 이루면서 최악의 시간복잡도인 O(n)을 가지게 됨
  이러한 경우 때문에 balanced binary search tree가 개발됨

Removing Elements from a BST

• 2단계로 구성
• Find 단계 :
  Comparator를 통해 root부터 시작해 제거하려는 원소를 찾음
  ( 0 찾음 / 1 더 큼 / -1 더 작음 / null 존재 x)
• Remove 단계 :
  successor를 통해 제거할 노드를 BST invariant를 충족하는 노드와 교체, 4가지 경우 존재
  • 1) 제거하려는 노드가 leaf 인 경우(자식 x)
  • 2) left subTree 존재하는 경우
  • 3) right subTree 존재하는 경우
  • 4) 두 subTrees 존재하는 경우
• 1의 경우 바로 제거
• 2,3의 경우 successor가 subTree의 root를 가리키고 제거하려는 노드 제거 후 그 자리에 successor가 가리키는 노드를 붙임
• 4의 경우 left subTree의 원소들 중 가장 큰 값(가장 오른쪽으로 내려가면 됨)이나 right subTree의 원소들 중 가장 작은 값(가장 왼쪽으로 내려가면 됨)을 successor로 가리키고 그 값을 제거할 노드값에 넣음
  => left subtree의 원소들보다 무조건 크고 right subTree 원소들보다 무조건 작으므로 BST invariant 만족

Tree Traversal

Tree 전체를 순회하는 방법

• preOrder(node) :
  if(node == null) return;
  printf(node.value);
  preOrder(node.left);
  preOrder(node.right);

• inOrder(node) :
  if(node == null) return;
  inOrder(node.left);
  printf(node.value);
  inOrder(node.right);

• postOrder(node) :
  if(node == null) return;
  postOrder(node.left);
  postOrder(node.right);
  printf(node.value);

• levelOrder :
  root 노드를 queue에 넣음
  while(!queue.IsEmpty()) :
  node = queue.poll();
  printf(node.value);
  if(node.left != null) :
  queue.push(node.left);
  if(node.right != null) :
  queue.push(node.right);