[DataStructure] Trees

DOM 또한 Tree data structure을 갖는다.
linked list도 tree 타입인데, single direction의 tree이다.

설명

BigO

• lookup, delete, insert 모두 O(logN) 이다.

hash table보다 나은 점

• preserve relationship를 갖고 있다는 것

unBalanced BST

• BST(Binary Search Tree)를 만들면, insert과정에서 전체 Tree의 밸런스가 맞지 않는 경우가 발생한다. 밸런스를 맞추는 방법으로는 AVL Tree, Red/Black Tree 등이 있다.

용어참고

검색해볼만한 단어들을 기록합니다.

• abstract syntax tree
• root, parent, child, leaf, silbling

Binary Heaps Tree

• priority queue 이다.
• max binary heaps라고 부르기도 한다. (min은 반대)
• 위에서 아래로 값의 순서를 보정하기 때문에, unbalance가 발생하지 않는다. 가장 빠를 때는, O(1)이다.
  (참고로 Heaps의 의미는 Heaps Memory와는 무관하다.)

Trie

re"trie"ve의 뜻으로, text search에 사용된다.
단어의 알파벳을 저장하고, 그것으로 tree를 만드는 방식이다.
원래 발음은 tree와 같지만, tree와의 혼동을 때문에, try라고 발음한다.

Code

Binary Search Tree Code (직접 작성)
https://replit.com/@devstefancho/binary-search-tree#index.js

Binary Search Tree Code (Udemy lecture version)
https://replit.com/@aneagoie/Data-Structures-Trees