Data Structure - Tree , Binary Tree, Binary Searching Tree

---

Tree 구조는 Graph Data Structure의 한 종류다. JavaScript에서 object(객체)는 Tree 구조와 매우 유사하다. Tree구조란 어떤 것인지, Binary Search Tree는 무엇인지에 대해 알아보자

---

우선적으로 Graph와 Tree에 대해 비교를 해보면 아래와 같다.

Tree Data Structure는 node로 이루어진 구조로서, 하나의 root node를 가진다. root node는 0개 이상의 child node를 가지고 있으며 그 child 또한 0개 이상의 child node를 가진다. 이러한 과정을 통해 나무 모양의 구조로 나타나는 특징이 있다.

node들은 서로 edge로 연결되어 구성되며 tree 구조에서는 cycle이 존재하지 않는다. tree 구조는 비선형 자료구조이며 계층적인 관계를 표현한다. 그래프의 한 종류로서, Directed Acyclic Graph(방향성 비순환 그래프)이며 Connected Graph이다.

---

tree 구조의 용어들을 보면 다음과 같다.

Root node : 부모가 없는 최상위 node, tree는 하나의 Root node를 가진다.
Leaf node : 자식이 없는 최하위 node, 말단 node, 잎 node 라고도 부른다.
Internal node : Root & Leaf node가 아닌 node.
edge : node와 node를 연결하는 선 (link, branch라고도 부른다.)
sibling : 같은 parent를 가지는 node.
size : 자신을 포함한 모든 child node의 개수
depth : root 에서 특정 node로 가기위에 거쳐야 하는 edge.
level : 트리의 특정 깊이를 가지는 node의 집합.
degree : 차수, 각 노드가 지닌 가지(branch)의 수. ( = 하위 트리 개수 / edge 수)
degree of tree : tree 구조의 최대 차수.
height : root node에서 가장 깊숙이 있는 node의 깊이.

---

Tree에는 Binary Tree, Binary Searching Tree, AVL Tree, red-black Tree, Completed Binary Tree, Full Binary Tree(Strictly Binary Tree), Perfect Binary Tree, Binary heap, Trie 등이 있다.

---

Tree Data Structure는 Graph Data Structure의 한 종류이므로, 마찬가지로 Adjacency List와 Adjacency Matrix를 통해서 표현이 가능하다.