Please enable JavaScript.

Coggle requires JavaScript to display documents.

INT320 : Data Structure (Graphs (Basic (V = Vertices (Node), E = Edges…

- - - - Find
      - Insert , Delete
      - FindMin ,FindMax
      - Height = lg n
  - - - LL
        
        ทางซ้ายของลูกตัวซ้าย
        
        จัดการโดยการ หมุนตามเข็มนาฬิกา (หมุนขวา) เป็นการหมุมแบบ Single Right Rotate
      - RR
        
        ทางขวาของลูกตัวขวา
        
        จัดการโดยการ หมุนทวนเข็มนาฬิกา (หมุนซ้าย) เป็นการหมุนแบบ Single Left Rotate
      - RL
        
        ทางซ้ายของลูกตัวขวา
        
        เพิ่มตัวซ้ายของลูกขวาา เอาตัวซ้ายที่เพิ่มเข้ามาหมุนขวาก่อนหนึ่งรอบ แล้ว Tree มันจะดูผิด ๆ คือ .. สามตัวจะเรียงกัน ให้หมุนซ้ายอีกรอบนึง เป็นอันเสร็จ
        
        ทริกซ์ก็คือ เอาตัวที่เพิ่มเข้ามานั่นแหละ ขึ้นมาเป็น Root .. แล้วเอา Root เดิมไปไว้ทางซ้ายของตัวใหม่แทน
      - LR
        
        ทางขวาของลูกตัวซ้าย
        
        เพิ่มตัวขวาของลูกซ้ายมา เอาตัวขวาที่เพิ่มเข้ามาหมุนซ้ายก่อนหนึ่งรอบ แล้ว Tree มันจะดูผิด ๆ คือ .. สามตัวจะเรียงกัน ให้หมุนขวาอีกรอบนึง เป็นอันเสร็จ
        
        ทริกซ์ก็คือ เอาตัวที่เพิ่มเข้ามานั่นแหละ ขึ้นมาเป็น Root .. แล้วเอา Root เดิมไปไว้ทางขวาของตัวใหม่แทน
  - - - Find, FindMin, FindMax, Insert, Delete
      - ใช้ BigO (Worst Time) เดียวกันหมดเลย
    - - Must Checking balance Everytimes ! เชคแม่งทุกรอบเลย
      - Adjustment มีการตัดสินใจตลอด
      - Code แม่งซับซ้อนเหี้ย ๆ !
- - - - Unsorted Array
      - Sorted Array
  - - - ShiftUp : O(log N) -- มันคือการสลับ Node ขึ้นไปเรื่อย ๆ หาก Node มีค่ามากกว่า Parent
      - การเพิ่ม Queue เข้าไปทางท้ายสุดของ Tree (Queue)
    - - การลบตัวบนสุดของ Tree (Queue)
      - ShiftDown : O(log N) -- มันคือการสลับ Node ลงมาเรื่อย ๆ หาก Node มีค่าน้อยกว่า Parent
- - - - เมื่อ Hashing ได้ Index เดียวกัน ให้เอาตัวที่มาทีหลัง มาแทนที่ตัวก่อนหน้า แล้วเอาตัวก่อนหน้า มาผูก Linked-list กับตัวที่มาทีหลังแทน
      - วิธีนี้จะเกิด Overflow Table Size
      - แม่งไม่ดี !
    - - เมื่อ Hashing แล้วได้ Index เดียวกัน มันจะข้ามไปดูอันต่อไปว่า !!!! ว่างไหม ถ้าว่าง ก็จะวางตรงนั้นแทน
      - แต่ถ้าไม่ว่าง มันจะเดินต่อไปอีกช่อง ช่องต่อไปเรื่อยๆ จนกว่าจะเจอที่ว่าง
      - วิธีข้างบนนี้คือ Linear probing
      - วิธีอื่น ๆ มีอีก 2 วิธี หากวิธีแรกมันจะช้าไป ~
        
        Quadratic probing
        
        วิธีนี้คือ เปลี่ยนจาก h(x) + i เป็น h(x)+i^2 แทน ทำให้มันจะกระโดดได้ทีละกำลังสองจ้า
        
        Double hashing
        
        วิธีนี้คือ การ Hashing 2 ชั้น จะเปลี่ยนจาก h(x) + i เป็น h(x) + i * g(x) วิธีนี้มันจะยิ่งซ้ำกันยากมาก ๆ ละแหละ ฮ่า ๆๆ แต่ก็ไม่ใช่ดีที่สุดนะ
- - - - Bubble Sort
        
        กลับกันกับ Insertion Sort
        
        มันจะเชคกับตัวที่อยู่ข้างหลังมัน ถ้ามันใหญ่กว่า มากกว่า .. มันจะ Swap กับตัวหลังของมันไปเรื่อย ๆ จนเจอตำแหน่งที่ใช่
      - Insertion Sort
        
        ง่ายสุด มันจะเชคตัวเอง กับตัวก่อนหน้า ไปเรื่อย ๆ ถ้าใช่ ก็ Swap
      - Selection Sort
        
        ตัวหน้า กับ ตัวหลัง สลับกัน เชคไปเรื่อย ๆ โดยที่มันจะไล่จากหลังมาหน้า
    - - Merge Sort
        
        แบ่งครึ่งไปเรื่อย ๆ จนเหลือแค่ 2 ตัว .. แล้วเอามาสลับกัน
        
        แล้วก็ Merge Array ไปเรื่อยๆ โดยเรียกจากน้อยไปหามากเหมือนเดิม
        
        ทำจนครบก้อนใหญ่
      - Quick Sort
        
        สุ่ม Pivot มาตัวหนึ่ง .. ปกติแล้วจะใช้ตัว Mid
        
        แบ่งข้อมูล 2 ชุด ชุดซ้าย S1 - น้อยกว่า pivot , ชุดขวา S2 - มากกว่า pivot
        
        เริ่มสลับ Pivot กับชุดขวา สลับ กับชุดซ้ายไปเรื่อย ๆ จนได้ S1, Pivot , S2
        
        เสร็จแล้วก็สลับกันภายใน S1 , S2 ต่อ จนครบ
      - แบ่งข้อมูลเป็น 2 ส่วน คือ คีย์ต่ำ และ คีย์สูง แล้วแยก ๆ เรียง ๆ แล้วค่อยเอามารวมกัน
- - - - ไม่มีลูกศร
      - ดูตัวอย่างง่าย ๆ คือ Topology ของ Network จ้า
      - ไป - กลับ ได้เรื่อย ๆ
    - - กราฟที่มีลูกศร มีหัว (Source) และ หาง (Destination)
      - Directed Acyclic Graphs คือ กราฟที่ไม่มี Cycle
        
        ทุก Tree คือ DAGs
        
        แต่ไม่ใช่ทุก ๆ DAGs เปน Tree นะ
    - - แสดงค่า หรือมี Label บอก
      - ไม่ว่าจะเป็น Node หรือ Egde ก็ได้
  - - - เริ่มจากจุดไหน ก็ mark ไว้ว่าไปมาแล้ว
      - ไล่ไปให้สุดในแต่ละทาง
      - ถ้ามีให้เลือก 2 ทาง ให้เลือกค่า cost น้อยกว่า
    - - สร้าง temp Priority Queue ขึ้นมา .. แล้วไล่เอาแต่ละอันเลย ว่าไปไหนได้บ้าง
      - ไปแบบ Breath-first เหมือน Tree เลย คือ เอาให้ครบก่อน แล้วลงลึกต่อไป
    - - จุดไหนที่มี in-degree เป็น 0
      - ไล่แล้ว ก็ลบออก ทั้ง node และ edges ของตัวนั้น .. แล้วก็เริ่มใหม่
  - - - *เหมือน OSPF
      - Dijkstra’s Algorithm (Greedy Algorithm)
      - เริ่มจากตัวไหนก็ได้ พอเริ่มปุ๊บ เราจะเดินตามทางค่า Cost ที่น้อยที่สุด
      - บวกค่า Cost เพิ่มขึ้นเสมอ ๆ จากจุดเริ่มต้นของเส้นทาง
      - ทำเรื่อย ๆ จนครบทุก Node
      - -- จะได้ตารางสุดท้าย เป็น Table ที่มีทั้งหมด N row และ 3 Column ซึ่ง ประกอบด้วย Know (T/F) / Cost / Precessor (มาจากตัวไหน)
    - - *เหมือน RIP
      - Floyd’s Algorithm
      - สร้าง Metrix ขึ้นมา เพื่อเก็บค่าทุกๆ อย่างเอาไว้ A - A , Z - Z
      - Learning ไปเรื่อย ๆ จนกว่าจะครบทุก Node
      - เนื่องจาก เป็น Directed Graph ดังนั้น จาก A->A จะไม่ใช่ 0 ถ้าไม่เป็น Loop ที่ A .. จะต้องหาทางวนมาหา A แล้วนับ Cost ให้ได้