• Tree

    Untitled

    • Binary Tree only 0,1,2 Child(ren)

      • Proper BT: only 0, 2 child(ren)
      • Full BT: Every level is full; 2^n -1
      • Complete BT: 좌→우로 차 있다

    • Traversal

      • Preorder Root, Tree(L), Tree(R)
      • Postorder Tree(L), Tree(R), Root
      • Inorder(has several definitions) Tree(L), Root, Tree(R)

    • Search

      • DFS(Depth First Search)

        • Go down first
        • Recursive implementation using STACK
        • Pre, post, inorder
        stack.push(root);
While(!empty){
	current=stack.pop();
	DFS(current->child1);
	DFS(current->child2);
	...
}

      • BFS(Breath First Search)

        • Go across
        • Implementation using QUEUE

    • Tree Implementation

      • Parent-Point (Two Linear Array) Parent: O(1) Leftmost child: O(n) 트리끼리 합치기 어렵다.

        Parent 0 1 1 2 2 2
        Label a b c d e f

        Untitled

      • List of Children Linked list based Combine tree: O(1)

      • only change the parent of each root Separate array combine: O(n) *DIfficult to access Right sibling(need to search linked list) *Space complexity: children appear in both array

        Untitled

      • Left-Child / Right-Sibling Static imlement(array): each node has parent, L.C, R.S information *fixed space

      Linked Implement(Linked List) Knuth Transform : convert into BINARY tree 1. Leftmost child →Left child (red) 2. Right Sibling→Right child (green) 3. Rotate 45 degrees

        ![Untitled](<https://s3-us-west-2.amazonaws.com/secure.notion-static.com/c5ee7853-3ca6-4f2a-a937-e48ddc78ee4c/Untitled.png>)
  
  Convert any tree into BINARY TREE
  *traversals
  preorder in tree → preorder in BT
  postorder          → Inorder
  Inorder              → postorder

      • Binary tree with two different traversals ex) Inorder + postorder, Inorder+preorder //post+pre: impossible [Unique] inorder hdibeafcg postorder hidebfgca; last one is root [a] hdibe fcg hideb fgc; root is [b], [c], are children of [a] hdi e f g hide fg ; [f][g] are children of c, [d] [e] are children of [b] h i h i ; [h][i] are children of [d]

        Untitled

  • Binary Search Tree (BST) (ordered BT) BST properties:

    1. Every node key is UNIQUE
    2. Ordered by KEY value
    3. All keys in left subtree < Root < all in R

    Search: O(height); O(log n) when balanced, O(n) when linear list Sort: inorder traversal→자동으로 됨; O(n)

    • Deletion in BST(complicated)

      • Degree 0 node(Leaf) :그냥 삭제

      • Degree 1 node(one child) Delete First, connect parent - child

        Untitled

      • Degree 2 node(two child) i) leftmost is leaf

        //done

        //done

        ii) leftmost is degree 1

        Untitled

    • Converting BT to BST
      1. Inorder traversal first
      2. Sort list
      3. copy list into original tree →Sorted!
    • Minimum / Max Node =Leftmost node, Rightmost node

  • Priority Queue Queue with Importance(priority) of KEY Insert: just insert Delete: Minimize+Delete →O(n)

    //seems bit slow! →HEAP

    //seems bit slow! →HEAP

  • Heap Tree-based Datastructure with HEAP property : priority(parent) < priority(Child) (min heap)

  • BINARY HEAP

    1. Complete binary tree(all levels without last level is full, last level is filled L→R)
    2. Min tree(heap property) →Min Heap
    • Insert(Up heap bubbling): O(log n)
      1. make hole in last position of level(height)
      2. check property→correct violation
    • Delete(Down heap bubbling): O(log n)
      1. delete root node
      2. take last node on tree into root position
      3. check property

    Untitled

    • Heapify 주어진 CBT를 Binary Heap으로 바꾸려면 그냥 모든 노드에 대해 check를 하면 되지만, 대신 nlogn이 걸리고 unique 하지 않다. →O(n)짜리 방법

      Untitled