為什么要有紅黑樹

想必大家對(duì)二叉樹搜索樹都不陌生，首先看一下二叉搜索樹的定義：
二叉搜索樹（Binary Search Tree），或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；它的左、右子樹也分別為二叉排序樹。
從理論上來說，二叉搜索樹的查詢、插入和刪除一個(gè)節(jié)點(diǎn)的時(shí)間復(fù)雜度均為O（log(n)）,已經(jīng)完全可以滿足我們的要求了，那么為什么還要有紅黑樹呢？
我們來看一個(gè)例子，向二叉搜索樹中依次插入（1，2，3，4，5，6），插入之后是這樣的

 

 

從2-3樹來看紅黑樹

一般我們接觸最多的是二叉樹，也就是一個(gè)父節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)。2-3樹與二叉樹的不同之處在于，一個(gè)父節(jié)點(diǎn)可以有兩個(gè)子節(jié)點(diǎn)，也可以有三個(gè)子節(jié)點(diǎn)，并且其也滿足類似二叉搜索樹的性質(zhì)。還有最重要的，2-3樹的所有葉子節(jié)點(diǎn)都在同一層，且最后一層不能有空節(jié)點(diǎn)，類似于滿二叉樹。
我們依次插入10，9，8，7，6，5，4，3，2，1來看一下2-3數(shù)是如何進(jìn)行自平衡的。
2-3樹在插入元素之前首先要進(jìn)行一次未命中的查找，然后將元素插入葉子節(jié)點(diǎn)中，之后再進(jìn)行平衡操作，下面具體說明。
首先插入10，如下圖

 

 

 

 

 

 

 

 

 

 

再看紅黑樹

那么紅黑樹與2-3樹有什么關(guān)系呢？現(xiàn)在我們對(duì)2-3樹進(jìn)行改造，改造成一個(gè)二叉樹。怎么改造呢？對(duì)于2節(jié)點(diǎn)，保持不變；對(duì)于3節(jié)點(diǎn)，我們首先將3節(jié)點(diǎn)中左側(cè)的元素標(biāo)記為紅色，如下圖2所示。