[4주차] Tree

Chen·2024년 5월 18일

tree 트리

Data Structure

목록 보기

5/10

1. Tree 개념

Node로 이루어진 자료구조로, 스택/큐와 같은 선형 구조(Linear)가 아닌 비선형(Non-linear) 구조

트리 = Node와 Link의 집합

(= 하나의 자료 뒤에 여러 개의 자료가 존재할 수 있는 형태)

자료들간의 앞, 뒤 관계가 1: n 또는 n:n의 관계를 나타내며, 계층적 구조를 나타내기에 적절
~~패드 있으면 뭐하나... 귀차는데...~~

여튼... HTML, React DOM을 떠올려보라

<html>
	<head>
    	<body>
        	<div></div>
			<div></div>
        </body>
    </head>
</html>

<html> 이 root Node고

root가 없더라도 임의로 root를 만들어주어 트리를 알고리즘에 활용할 수 있음
(or 최종적으로 <> </>로 wrapper을 만들면 됨)

일상생활/프로그램에서 정말 많이 쓰이는 구조

Tree는 가지에 개수 제한이 없음
=> 너무 많은 가지가 나오면 알고리즘으로 활용하기 어려움
=> 가지 개수에 제한을 줌
ex. 이진 트리 binary tree (가지 0~2개) => (검색/정렬)

각각의 Node 마다 children 개수가 다 달라서 알고리즘을 통일되게 적용하기 어려움

=> 단순 Tree구조에서는 신나게 push()하는 느낌이라 특별한 게 없음..ㅋㅋ
=> 그래서 레드블랙트리, AVL 트리, 이진 트리, 이진 탐색 트리 등 여러 종류가 있음

용어

	Root
	Edge(링크)

	Leaf nodes (자식 없는 Node)

*** Sub Tree ***
	Parent Node
	Child Node
	Siblings (같은 레벨)

*** Height ***
	Level

2. Tree 구현하기

class Tree {
  constructor(value) {
    this.root = new Node(value);
  }
}

class Node {
  children = []; 
  constructor(value) {
    this.value = value;
  }

  push(value){
    this.children.push(new Node(value)); 
    // new Node(value) 푸시하는 이유 = 자식도 children 가질 수 있게끔
  }
}

const tree = new Tree(50);

실행결과

const tree = new Tree(50);

tree.root.push(1);
tree.root.push(2);

console.log(
  tree.root.children,
  /* 
  [
  	Node { children: [], value: 1 }, 
    Node { children: [], value: 2 }
  ]
  */
  tree.root.children[0].value, // 1
  tree.root.children[1].value, // 2
)

tree.root.children[0].push(30);
tree.root.children[1].push(31);

console.log(
  tree.root.children[0],
  /*
  	Node { 
    	children: [
        	Node { children: [], value: 30 } 
        ], value: 1 } Node
  */
  
  tree.root.children[1],
  /*
  	Node { 
    	children: [ 
        	Node { children: [], value: 31 } 
       	], value: 2 }
  */
)

Chen

현실적인 몽상가

이전 포스트

[4주차] Queue

다음 포스트