分類 "C++系列" 下的文章

二叉搜尋樹概念二叉搜尋樹又稱二叉排序樹，它可能是一棵空樹，或者是具有以下性質的二叉樹左子樹如果不為空，則左子樹的值一定小於等於根節點右子樹如果不為空，則右子樹的值一定大於等於根節點每個根節點的左右子樹也滿足以上性質二叉搜尋樹時間複雜度分析最優情況：二叉搜尋樹整個樹的結構為完全二叉樹或接近完全二叉樹 => O(logN) ( 其中 N 為樹的高度 )最壞情況：如果插入的資料的順序接近或就是有序...

AVL樹介紹AVL 樹 也稱為平衡二叉搜尋樹，其在一般二叉搜尋樹基礎上加入了平衡因子，平衡因子的有效範圍在[-1, 1]之間，假如超過這段區間，則此樹即不平衡，就必須藉由旋轉來調整，使其恢復平衡。AVL樹實現AVL樹基本結構// 每個節點包含：左子節點指標、右子節點指標、父節點指標、鍵值對資料、平衡因子 template <class K, class V> struct AVLNod...

雜湊的概念雜湊，也稱「散列」是一種用來進行高效查找的資料結構，查找的時間複雜度平均為O(1)，其本質就是依賴雜湊函數這個演演算法來將 key和該key儲存位置建立一個映射關係。而因為是有著映射關係，所以雜湊的時間複雜度為O(1)。key => hash function => position採用雜湊處理時，一般所需空間都會比元素個數多，否則產生衝突的機率就比較大，影響雜湊的效能 =&...

setset 容器介紹set屬於關聯容器(Associative Container)，其按照某種排序方式排序且儲存的元素是唯一的預設情況下set按照key進行升序排序，可以藉由仿函式來變更其排序的方式set 的底層實現是二叉搜尋樹，因此 set 不提供更改資料的接口，避免更新破壞二叉搜尋樹的特性// Example int main() { set<int> s; // 空set s...

什麼是vectorvector是C++提供的一個容器(container)，其底層邏輯類似於順序表vector 接口宣告 && 初始化std::vector<int> v; // 空 vector std::vector<int> v(5); // 初始化為 5 個 0（不給值預設為0) std::vector<int> v(5, 10); // 初始化為 5 ...