[자료구조] 이진트리

1. 트리

연결리스트는 선형으로 한가지를 선택한다.

반면에 트리는 비선형으로 여러가지 선택을 할수 있다.

트리는 무조건 자식 노드만 가리켜야 하고 부모나 형제를 가리킬수 없다는 규칙이 있다.

 

트리 예시

2. 이진트리

트리중 이진 트리는 부모가 가질수 있는 최대 자식노드는 2개이다.

따라서 노드는 2개 이하의 자식노드를 가질 수 있다.

또한 이진트리는 자기보다 작은수는 왼쪽, 큰수는 오른쪽에 배치한다는 특징을 가지고 있다.

출처 : 위키디피아

3. 트리 용어

root : 꼭대기 노드

child : 자식 노드

parent : 부모 노드

siblings : 부모가 같은 자식들

leaf : 자식이 없는 노드

edge :  노드에서 다른 노드로 향하는 화살표

 

4. 이진트리 클래스

(1) 클래스 및 노드

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
}

(2) insert

insert(val) {
    let newNode = new Node(val);
    if (!this.root) {
      this.root = newNode;
      return this;
    }

    let current = this.root;
    while (true) {
      if (val === current.value) return undefined;
      if (current.value < val) {
        if (!current.left) {
          current.left = newNode;
          return this;
        }
        current = current.left;
      }

      if (current.value > val) {
        if (!current.right) {
          current.right = newNode;
          return this;
        }
        current = current.right;
      }
    }
  }

(3) find

find(val) {
    if (!this.root) return false;
    let current = this.root,
      found = false;
    while (current && !found) {
      if (val < current.value) {
        current = current.left;
      } else if (val > current.value) {
        current = current.right;
      } else {
        found = true;
      }
    }
    return found ? current : undefined;
  }

5. 이진트리 빅O

insertion(삽입)	searching(탐색)
O(logn)	O(logn)