?二叉樹和紅黑二叉樹
二叉樹的定義
二叉樹是樹形結(jié)構(gòu)的一個重要類型凉夯。 許多實際問題抽象出來的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹的形式性雄，即使是一般的樹也能簡單地轉(zhuǎn)換為二叉樹疹娶，而且二叉樹的存儲結(jié)構(gòu)及其算法都較為簡單负蚊，因此二叉樹顯得特別重要。
二叉速樹的特點：
1)樹是由一個集合以及在該集合上定義的一種關(guān)系構(gòu)成的鞋仍。
集合中的元素稱為樹的結(jié)點，所定義的關(guān)系稱為父子關(guān)系搅吁。
2) 父子關(guān)系在樹的結(jié)點之間建立了一個層次結(jié)構(gòu)威创。
3) 樹的結(jié)點包含一個數(shù)據(jù)元素及若干指向其子樹的若干分
支。
4) 在這種層次結(jié)構(gòu)中有一個結(jié)點具有特殊的地位谎懦，這個結(jié)點
稱為該樹的根結(jié)點肚豺，或簡稱為樹根。
平衡二叉樹
在平衡二叉樹中任何節(jié)點的兩個子樹的高度最大差別為1界拦，所以它也被稱為高度平衡樹吸申。 增加和刪除節(jié)點可能需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個樹。
?紅黑二叉樹
紅黑二叉樹(簡稱：紅黑樹)享甸，它首先是一棵二叉樹截碴，同時也是一棵自平衡的排序二叉樹。
? ? ??紅黑樹在原有的排序二叉樹增加了如下幾個要求：
? ? ??1. 每個節(jié)點要么是紅色蛉威，要么是黑色日丹。
? ? ??2. 根節(jié)點永遠(yuǎn)是黑色的。
? ? ??3. 所有的葉節(jié)點都是空節(jié)點(即 null)蚯嫌，并且是黑色的哲虾。
? ? ??4. 每個紅色節(jié)點的兩個子節(jié)點都是黑色割坠。(從每個葉子到根的路徑上不會有兩個連續(xù)的紅色節(jié)點)
? ? ??5. 從任一節(jié)點到其子樹中每個葉子節(jié)點的路徑都包含相同數(shù)量的黑色節(jié)點。
? ? ??這些約束強化了紅黑樹的關(guān)鍵性質(zhì)：從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長妒牙。這樣就讓樹大致上是平衡的彼哼。
? ? ??紅黑樹是一個更高效的檢索二叉樹，JDK 提供的集合類 TreeMap湘今、TreeSet 本身就是一個紅黑樹的實現(xiàn)敢朱。
TreeMap的使用和底層實現(xiàn)
TreeMap和HashMap實現(xiàn)了同樣的接口Map，因此摩瞎，用法對于調(diào)用者來說沒有區(qū)別拴签。HashMap效率高于TreeMap;在需要排序的Map時才選用TreeMap。
HashSet
其特點為：是無序旗们、不可重復(fù)
HashSet與HashMap的關(guān)系蚓哩？
?HashSet是采用哈希算法實現(xiàn)，底層實際是用HashMap實現(xiàn)的(HashSet本質(zhì)就是一個簡化版的HashMap)上渴，因此岸梨，查詢效率和增刪效率都比較高。
TreeSet的底層數(shù)據(jù)結(jié)構(gòu)是：紅黑樹稠氮，通過內(nèi)部比較器和外部比較器去掉重復(fù)元素曹阔。
Hashset自定義對象時，必須重寫hashcode()方法和equals()方法隔披，以下為課堂代碼
TreeSet的使用和底層實現(xiàn)
TreeSet底層實際是用TreeMap實現(xiàn)的赃份，內(nèi)部維持了一個簡化版的TreeMap，通過key來存儲Set的元素奢米。 TreeSet內(nèi)部需要對存儲的元素進(jìn)行排序抓韩，因此，我們對應(yīng)的類需要實現(xiàn)Comparable接口鬓长。這樣谒拴，才能根據(jù)compareTo()方法比較對象之間的大小，才能進(jìn)行內(nèi)部排序痢士。
TreeSet的使用
運行結(jié)果為：
遍歷集合的方法總結(jié)
遍歷List方法一：普通for循環(huán)?
?
遍歷List方法二：增強for循環(huán)(使用泛型!)
遍歷List方法三：使用Iterator迭代器(1)
遍歷List方法四：使用Iterator迭代器(2)
遍歷Set方法一：增強for循環(huán)
遍歷Set方法二：使用Iterator迭代器
遍歷Map方法一：根據(jù)key獲取value
遍歷Map方法二：使用entrySet
集合體系框架總結(jié)表如下：
