一、 平衡二叉樹：除葉子節點外，任意節點的子樹高度之差不超過1。
二、完全二叉樹：除了最底下一層外，每層都是滿節點，最底下一層節點是從左到右排列的。
三、二叉搜索樹：左兒子val<父節點val<右兒子val
四、紅黑樹
紅黑樹有哪些性質？
1. 只有紅色和黑色兩種節點；
2. 根節點是黑色的；
3. 葉子節點是null節點並且是黑色的；
4. 紅色節點的兩個兒子都是黑色的；
5. 對於任意一個節點，它到其葉子節點的所有路徑上有相同數量的黑節點；
由上面這些性質，可以推導出紅黑樹任意節點到以其為子樹的葉子節點最長路徑長度不超過最短路徑長度的2倍。解釋一下，為了使最長路徑和最短路徑差距盡可能大，我們不能增加黑色節點的數量，因為兩條路徑上的黑色節點數量應該是相同的，所以會同時增加，應該增加紅色節點的數量，但是由於紅色節點的兒子必須是黑色節點，因此最長路徑之只能是紅黑交替的，加之最短路徑上的黑色節點數量是和最長路徑上相同的，所以最長路徑的長度不會超過最短路徑長度的2倍。
2. 紅黑樹相比BST和AVL有哪些優勢？
相比AVL的高度平衡，紅黑樹並不是高度平衡的，通過旋轉，任何不平衡都可以在三次旋轉之內解決，插入和刪除這些動態操作維護起來比AVL容易，對於數據分布較好的情況可以使用AVL，如果數據分布比較隨機那麼用紅黑樹較好。
相比於BST可能退化成一條鏈，紅黑樹可以保證最長路徑的長度不超過最短路徑長度的2倍，最壞情況下仍是O(logn)的操作復雜度，而BST最壞情況下查找復雜度是O(N)的。
3. 什麼時候用hash什麼時候用map？
要根據查找速度、數據規模、內存使用和可擴展性幾個方面去綜合權衡。
總的來說哈希的速度要比map速度快，因為哈希是常數復雜度，而map是O(logn)的，但是hash更耗內存。如果數據都是靜態的，不會動態的添加和刪除，那麼就構建一個hash表。如果數據是動態的，那麼就用map。
通過統計以每個節點為根節點的子樹中的節點個數，可以求某個數的秩和第k大的數。
五、空間劃分樹
1. 四叉樹
主要用來管理二維平面上的點對象，首先整個平面作為四叉樹的根節點，然後將平面分成四份，每份作為根節點的一個兒子，然後再對每個子平面做同樣的劃分。這種數據結構一般用來動態查詢某個區域內包含哪些點對象，主要是用來剪枝的，比如說查詢一個圓內包含哪些點，那麼就從根節點開始，判斷當前節點所表示的矩形區域是否在圓內，如果在，則區域內所有點都在，如果完全不在圓內，那麼可以進行剪枝，不用再繼續往下搜了，如果部分在，那麼就繼續往下搜他的子孫節點。
n個節點的四叉樹每個節點都有四個指針，那麼空指針的個數是3n+1個，首先n個節點，那麼指針一共有4n個，除了根節點外，每個節點都有一個指針指向它，那麼總共有n-1個指針不是空指針，剩下的都是空指針，也就是4n-(n-1)=3n+1個。
2. 八叉樹
原理和四叉樹是一樣的，只不過它是用來管理三維區間的，也就是把一個立方體區域劃分為8個子立方體，剩下的和四叉樹一樣。
3. kd樹
k緯空間劃分樹，采用分治建樹的思想，每一層遍歷L~R的所有點，找出這些點在某一維上的最大距離差，然後就以每個點在這一維度上的坐標進行排序，其實不用完美的排序，只要保證找到排序後的中間點，然後把所有不大於它的點放到左邊，所有不小於它的點放到右邊，然後再對兩邊的數組進行同樣的遞歸操作。這樣最終可以得到一棵平衡二叉樹。
查找的時候，如果是查距離某個點最近的k個點，先將這個點和當前區間的中間點求個距離，然後扔到優先隊列裡面，保證優先隊列中只有k個元素，然後求這個點和中間點在當前劃分維度（通過之前建樹的時候所選取的中間點來記錄劃分維度）上的相對位置，如果小於就在左兒子找，如果大於就在右兒子找，另外還得求下查找點和中間點在劃分維度上的距離，如果優先隊列中的距離有比這個還大的，那就還得在另一個兒子中找，我是這樣理解的，主要是因為如果當前優先隊列裡面維護的距離超過了它們在當前維度上的距離，那麼就可以以查找點為圓心，以優先隊列裡那個距離為半徑畫個圓，這個圓和左右兩個兒子表示的區間都有交集，所以兩個兒子中的點都可能比優先隊列中的更短，都得搜一下。
對於查找一個圓（或者球，這裡就討論這兩種吧。。。）包含哪些點。。下面的解法是我自己YY的。。。
求圓心（或者球心）和中心點在當前劃分維度上的距離，如果這個距離比半徑小那就兩個子區間都查詢（因為和兩個子區間都有交集），否則小於中心點只查左兒子，大於查右兒子。
注意上面這三種數據結構都是用來對動態查詢進行剪枝的。。。不要想著復雜度能多優越。。。
