期中考考試Stack-Queue-LinkedList-SearchTree

資料結構-Binary search練習題期中複習

資料結構-SearchTree期中複習

SearchTree:較小的數字在左邊,大的數字則在右邊

資料結構-LinkedList期中複習

LinkedList:就像珍珠一顆一顆的串在一起

資料結構-Queues期中複習

Queues:就像排隊買票,排在前面的先買

資料結構-Stack期中複習

Stack:像放盤子一樣,先放的後出,而後放的先出

二元搜尋樹

二元搜尋樹 ( binary search tree ) 是一種二元樹。
它可能是空的，若不是空的，它具有下列特性：
(１) 每一個元素有一鍵值，而且每一元素的鍵值都不
相同，即每一個鍵值都是唯一的。
(２) 在非空的左子樹上的鍵值，必小於在該子樹的根
節點中的鍵值。
(３) 在非空的右子樹上的鍵值，必大於在該子樹的根
節點中的鍵值。
(４) 左子樹和右子樹也都是二元搜尋樹。

使用Excel模擬二元搜尋的方法

Binary Search (二元搜尋法)
必須先將資料庫之資料進行排序
搜尋效率: Worst Case: O(Log2N)
搜尋方法: (假設資料庫已排序好, 由小排到大)
1. 找出搜尋範圍之中間位置之資料和key比較, 若相等則找到資料,結束搜尋
2. 若不相等, 再比較key是否小於中間位置之資料若是, 則將搜尋範圍縮小到左半邊
若否, 則將搜尋範圍縮小到右半邊
3. 重覆前述兩個步驟, 直到找到資料或搜尋範圍內無資料為止
資料庫新增資料: O(N) (將新增資料排序好)