Tree(트리) ✍🏻

Tree(트리)📍

---

• 자료구조 Tree는 이름 그대로 나무의 형태를 가지고 있다.
• 정확히는 나무를 거꾸로 뒤집어 놓은 듯한 모습을 가지고 있다.
• 그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조라 부른다.

• 트리 구조는 루트(Root) 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결한다.
• 각 데이터를 노드(Node) 라고 하며, 두개의 노드가 상하계층으로 연결되면 부모/자식 관계를 가진다.
• 위 그림에 부모 노드(Parent Node), 자식 노드(Child Node) 가 있으며, 자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(leaf Node)라고 부른다.

용어정리

• 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
• 루트(Root) : 트리 구조의 시작점이 되는 노드
• 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
• 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
• 리프(Leaf) : 트리 구조의 끝지점이고, 자식 노드가 없는 노드

Tree의 특징📌

깊이(Depth)

• 트리 구조에서 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현
• 루트 노드는 지면에 있는 것처럼 깊이가 0이다.
• 위 그림에서 루트 56의 depth는 0이고, 30과 70의 깊이는 1이다. 22, 40, 60, 95의 깊이는 2이다.

레벨(Level)

• 트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현할 수 있다.
• depth가 0인 56의 level은 1이다.
• depth가 1인 30과 70의 level은 2이다.
• 22, 40, 60, 95의 level은 3이고, 같은 레벨에 나란히 있는 노드를 형제 노드(sibling node)라고 한다.

높이(Height)

• 트리 구조에서 리프 노드를 기준으로 루트까지의 높이(height)를 표현할 수 있다.
• 리프 노드와 직간접적으로 연결된 노드의 높이를 표현하며, 부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로 가진다.
• 트리 구조의 높이를 표현할 때에는 각 리프 노드의 높이를 0으로 놓는다.

서브 트리(Sub Tree)

• 트리 구조에서 Root에서 뻗어나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리를 서브 트리 라 한다.

트리의 실사용 예제📌

• 가장 대표적인 예제는 컴퓨터의 디렉토리 구조이다.
• 어떤 프로그램이나 파일을 찾을 때, 바탕화면 폴더나 다운로드 폴더 등에서 다른 폴더에 진입하고, 또 그 안에서 다른 폴더에 진입하면서 원하는 프로그램이나 파일을 찾는다.
• 모든 폴더는 하나의 폴더(루트 폴더, /)에서 시작되어, 가지를 뻗어나가는 모양새를 띈다.

  트리의 또 다른 예시
  월드컵 토너먼트 대진표, 가계도(족보), 조직도 등

BST 만드는 방법📌

삽입 : 이 메서드는 값을 수락하고 새 노드를 만든다. 노드가 생성되면 이 메서드는 일련의 검사를 통해 노드가 왼쪽에 있는 낮은 값과 오른쪽에 있는 높은 값의 기준을 충적하는 위치에 배치되어 있는지 확인한다. 값이 이미 있는 경우 메서드는 undefined를 반환한다.

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

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

let bst1 = new BinarySearchTree()
let node1 = new Node(1)

bst1 // BinarySearchTree {size: 0, root: null}
node1 // Node {val: 1, left: null, right: null}

조회 : 프로세스는 트리에서 노드를 찾기 위해 유사한 검사를 통해 실행된다.
노드가 존재하지 않는 경우 메서드는 undefined를 반환한다.

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

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

  insert(val){
    let newNode = new Node(val)
    if(!this.root){
      this.root = newNode
      this.size++
      return this
    }
    let current = this.root
    while(true){
      if(val === current.val) return undefined
      if(val < current.val){
        if(!current.left){
          current.left = newNode
          this.size++
          return this
        } else {
          current = current.left
        }
      } else if (val > current.val){
        if(!current.right){
          current.right = newNode
          this.size++
          return this
        } else {
          current = current.right
        }
      }
    }
  }

  lookup(val){
    if(!this.root) return undefined
    let current = this.root
    while(true){
      if(val === current.val) return current
      if(val > current.val){
        if(!current.right) return undefined
        current = current.right
      } else if (val < current.val){
        if(!current.left) return undefined
        current = current.left
      }
    }
  }
}

let bst = new BinarySearchTree()
bst.insert(10)
bst.insert(6)
bst.insert(3)
bst.insert(8)
bst.insert(15)
bst.insert(20)
bst // BinarySearchTree {size: 6, root: Node}
bst.lookup(10) // Node {val: 10, left: Node, right: Node}
bst.lookup(3)  // Node {val: 3, left: null, right: null}

Tree 자료구조

class Tree {
  constructor(value) {
		// constructor로 만든 객체는 트리의 Node가 됩니다.
    this.value = value;
    this.children = [];
  }

	// 트리의 삽입 메서드를 만듭니다.
  insertNode(value) {
		// 값이 어떤 이름으로 만들어지고 어느 위치에 붙는지 떠올리는 것이 중요합니다.
		// TODO: 트리에 붙게 될 childNode를 만들고, children에 넣어야 합니다.
    const childNode = new Tree(value);
    this.children.push(childNode);
  }

	// 트리 안에 해당 값이 포함되어 있는지 확인하는 메서드를 만듭니다.
  contains(value) {
		// TODO: 값이 포함되어 있다면 true를 반환하세요. 
    if (this.value === value) {
      return true;
    }
		// TODO: 값을 찾을 때까지 children 배열을 순회하며 childNode를 탐색하세요.
	  for (let i = 0; i < this.children.length; i++) {
      const childNode = this.children[i];
        if (childNode.contains(value)) {
          return true;
    }
		// 전부 탐색했음에도 불구하고 찾지 못했다면 false를 반환합니다.  
    
  }
  return false;
}
}