回覆列表
-
1 # 此生唯一
-
2 # 知了爸爸
簡單來說，所有的資料結構都是為了增刪改查，那麼陣列/連結串列等線性表的優缺點分別是什麼呢？
這個時候，就需要一個折中方案的產生，此時二叉樹就既有連結串列的好處，也有陣列的好處。
在處理大批次的動態的資料是比較有用。
檔案系統和資料庫系統一般都採用樹（特別是B樹）的資料結構資料，主要為排序和檢索的效率。
平衡二叉樹都有哪些應用場景
二叉樹支援動態的插入和查詢，保證操作時間在Olog(n)內完成，n為節點數。
線性表與二叉樹優缺點比較：
順序儲存可能會浪費空間(在非完全二叉樹的時候)，但是讀取某個指定的節點的時候效率比較高O(1)
鏈式儲存相對二叉樹比較大的時候浪費空間較少，但是讀取某個指定節點的時候效率偏低O(nlogn)
樹和連結串列都是資料結構中比較常見的儲存模型，使用什麼作為儲存的資料結構根據場景，需求而定。
連結串列是什麼？想象一根腳踏車鏈條，從中間折斷，從一端到另一端剛好就是單向連結串列結構，在JAVA中每個連結串列節點作為一個類，屬性為自身的資料和下一個節點的引用，一扣接一扣成為一張連續的連結串列！
連結串列的查詢和刪除，修改都需要從頭部一個一個比較節點資料，直到找到匹配的那個數為止，很明顯這樣的查詢次數大概為N/2(N為連結串列節點總數)，也就是查詢的效率使用大O表示法表示為O(N)，線性級別;一個總數為N＝1024的連結串列需要平均比較512次才能做後面的增刪改操作，而修改和刪除只需要改變節點引用，效率很高！
再來看樹結構(以紅黑樹為例)，就是生活中的樹倒過來，所有的資料掛在根節點上，透過一定的策略(紅黑樹透過旋轉，變色等，二叉搜尋樹透過比較父節點)放置在合適的位置上，通常樹的深度都是常數級;
以上樹結構舉例使用紅黑樹，是因為紅黑樹是一種效能良好的平衡樹，如果是二叉搜尋樹(規則為比父節點小的放在左子節點，大的放右子節點)，如果插入的資料為順序的，則二叉搜尋樹就退變為一個連結串列結構，效率降低！換句話說不是說樹結構的查詢效率一定比連結串列好！
在資料量很低的時候，推薦使用連結串列，因為資料結構簡單，開發成本低，效率也不差！
在資料量大的時候，使用平衡樹結構的效率提升是顯而易見的，從O(N)到O(log2n)的提升。
在JAVA8中，當hashMap的衝突(某個陣列元素中的連結串列結構很長)達到一定值的時候，將會從連結串列結構轉變為紅黑樹，提高hashMap的查詢效能。