tree

Tree

중요한 이유?
현실세계와 많이 닮음. 부모와 자식간의 관계, 파일시스템 등
부모와 자식간의 복종 관계를 나타내고, 서비디렉토리는 부모 디렉토리에 포함됨

특징?
- dynamic data structure (추가하기 쉬우며 지우기 쉽다.)
- linked structure

트리 정의?
- root, parent, child, leaf
- signle root, no cycles in a tree, each node can have one parent

트리 종류?
- generic tree
- binary tree - each nood needs : parent, value, left,ritht child

구현 방법?

public class BinaryTree {
     TreeNode root;

     // method
     // pre-order
     // post-order
}

public class TreeNode {
     private E vale;
     private TreeNode parent;
     private TreeNode left;
     private TreeNode right;

     public TreeNode(E value, TreeNode parent) {
        // ...
     }

     // addLeftChild
     // addRightChile
}

traversals?
- visit data in different ways or in different ordering
- social network, maze game

pre-order traverslas
- visit yourself
- visit all your sub-left-tree
- visit all your sub-right-tree

post-order traverslas
- yourself - right - left

in-prder traverslas
- left - yourself - right

level-order(BFS)
- keep a list and keep adding to it and removing from start, we used this list like a 'queue'

pre-order, post-order are DFS

binary search
- log n
- sorted arrays are good for search but bad for insertion/removal
arrays cannot be dynamically resized either
so we use binary search tree

BST
- binary tree
- left subtrees are less than parent
- right subtrees are grater than parent