什么是“平衡二叉查找樹”?
二叉樹中任意一個節(jié)點的左右子樹的高度相差不能大于1。
平衡二叉查找樹中“平衡”的意思薛训，其實就是讓整棵樹左右看起來比較“對稱”媒吗、比較“平衡”，不要出現(xiàn)左子樹很高乙埃、右子樹很矮的情況闸英。這樣就能讓整棵樹的高度相對來說低一些，相應(yīng)的插入介袜、刪除甫何、查找等操作的效率高一些。
如何定義一顆“紅黑樹”遇伞？
- 根節(jié)點是黑色的辙喂；
- 每個葉子節(jié)點都是黑色的空節(jié)點（NIL）,也就是說 葉子節(jié)點不存儲數(shù)據(jù)；
- 任何相鄰的節(jié)點都不能同時為紅色，也就是說巍耗，紅色節(jié)點是被黑色節(jié)點隔開的秋麸；
-
每個節(jié)點，從該節(jié)點到達(dá)可達(dá)葉子節(jié)點的所有路徑芍锦，都包含相同數(shù)目的黑色節(jié)點竹勉；
紅黑樹
問題引出：為什么工程中都喜歡用紅黑樹，而不是其他平衡二叉查找樹呢娄琉？
AVL樹（平衡查找二叉樹）是一種高度平衡的二叉樹次乓，所以查詢的效率非常高，但是孽水，有利有弊票腰，AVL樹為維持這種高度的平衡，就要付出更多的代價女气。每次插入杏慰、刪除都要做調(diào)整，就比較復(fù)雜炼鞠、耗時缘滥。
而紅黑樹只是做到了近似平衡，并不是嚴(yán)格的平衡谒主，所以在維護(hù)平衡的成本上朝扼，要比AVL樹要低。紅黑樹的插入霎肯、刪除擎颖、查找各種操作性能都比較穩(wěn)定,其時間復(fù)雜度都為O（logn）。符合工業(yè)級工程的要求观游。
