[Tree][leetcode] 트리 개념 재정리 with GIF.

릿코드로 다시 data structure 와 algorithms 강의를 하루에 하나씩 듣고있는데 트리부분에 도착하였다! 이번에는 담담히 넘어가보자. 갈 길이 아직멀다...

 

면접에서 가장 흔하게 나온다는 tree 구조!  binary tree를 많이 사용하는데 이는 root(꼭대기 부터 2가지고 갈라져 나오기때문). 구조는 linked list에서 다뤘던것처럼 포인터가 다른 노드를 가르키고 있으며 여기서는 children 을 가르킨다고 한다. (parent 노드는 2개의 childeren 노드를 가지고있다)

 

너무 좋은 gif 표기

 

트리 구조는 일상생활에서 많이 사용되는데  :: 등이있다

• File system
• A comment thread on an app like Reddit or Twitter
• A company's organization chart

---

Code 표기법을 알아보자

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};

linked list와 유사한 구조를 가지고있는것을 확인할 수 있다!. linked는 next 노드 하나밖에 가르키는 포인터밖에없었지만 여기서는 left, right가 있다. 

 

---

추가로 저기 gif를 가져온 곳에서 좋은 자료들이있어 표기해본다.   출처

5 Gifs to Understand Binary Search Trees

 

1. BINARY SEARCH TREE FROM SORTED ARRAY

BINARY SEARCH TREE FROM SORTED ARRAY

 

2. INSERTION INTO A BINARY SEARCH TREE (BST) WORKS

INSERTION INTO A BINARY SEARCH TREE (BST) WORKS

3. DEGENERATION OF BINARY SEARCH TREE DEMONSTRATION

DEGENERATION OF BINARY SEARCH TREE DEMONSTRATION