java中的資料結構平衡二叉樹和紅黑樹

平衡二叉樹是左邊子節點比父節點小，右邊子節點比父節點大，左節點深度和右節點深度相同，或者右節點深度跟左節點深度相差1，比較嚴苛，需要不斷的變化，使得二叉樹平衡，損壞性能CPU。

紅黑樹是相對寬松的平衡二叉樹，最差情況下，右節點深度跟左節點深度相差2倍，包含内容：

1，樹節點隻有紅節點和黑節點

2，根節點必須是黑節點

3，葉子節點值即使是null，也必須是黑節點（意思是一半以上黑節點）

4，新插入的節點必須是紅節點

5，紅節點的子節點必須是黑節點

6，從任意一個節點出發到葉子節點的路徑上黑節點個數總和必須相同（假如全部是黑節點，就是節點數相同，最差情況下，假如一邊是黑節點，沒有紅節點，而另一邊有紅節點和黑節點，因為紅節點子節點必須是黑節點，是以他們交替出現，因為葉子節點必須是黑節點，是以一邊是5個節點，另一邊是10個節點，他們相差一半）

 上圖是紅黑樹操作規則：

1，其中類型表示目前節點是怎麼從祖父節點搜尋到父節點，再從父節點搜尋到孫子節點，可能父節點是在祖父節點的右邊，孫子節點又是父節點的右子節點，是以是右右類型，假如孫子節點是父節點的左邊子節點，就是右左類型，假如祖父節點的子節點是左邊子節點，孫子節點是父節點的左子節點，則是左左類型，如果孫子節點是父節點的右子節點，則是左右類型。

2，左旋表示以目前節點的父節點為支點，向左邊旋轉，這時父節點變為祖父節點，原來的祖父節點變為子節點，目前節點由原來的孫子節點變為子節點。比如a->b->c，左旋之後變為b->a，b->c。假如隻有兩個節點a->b，左旋之後，原來的父節點變為子節點，子節點變為父節點。

連結：​​https://www.ixigua.com/i6835579764477002247/​​