資訊專欄INFORMATION COLUMN
摘要：寫在前面紅黑樹(shù)，對(duì)很多童鞋來(lái)說(shuō)，是既熟悉又陌生。每次需要查看紅黑樹(shù)內(nèi)容時(shí)都很難以更生動(dòng)形象的方式來(lái)理解其內(nèi)容。
寫在前面
紅黑樹(shù)，對(duì)很多童鞋來(lái)說(shuō)，是既熟悉又陌生。學(xué)校中學(xué)過(guò)，只了解大概；工作中不怎么使用，但面試又是重點(diǎn)。每次需要查看紅黑樹(shù)內(nèi)容時(shí)都很難以更生動(dòng)形象的方式來(lái)理解其內(nèi)容。沒(méi)錯(cuò)，本文內(nèi)容就是要解決這個(gè)問(wèn)題，用簡(jiǎn)單的語(yǔ)言，搭配靜圖和動(dòng)圖(利用大腦圖形記憶方式)，讓你對(duì)紅黑樹(shù)有更深入的了解和更清晰的記憶，希望小伙伴們?cè)俅斡龅郊t黑樹(shù)的問(wèn)題不至于頭大，建議讀該文章姿勢(shì): 打開(kāi)兩個(gè)頁(yè)面，一個(gè)頁(yè)面看圖片和內(nèi)容，一個(gè)頁(yè)面看公式，像玩魔方一樣，多玩幾次就明白了
通過(guò)工具 (公眾號(hào)回復(fù)「工具」—>那些可以提高效率的工具—>紅黑樹(shù)) 動(dòng)態(tài)感受紅黑樹(shù)的轉(zhuǎn)換過(guò)程
俺家司令買完?yáng)|西后，我倆經(jīng)常會(huì)發(fā)生這樣的一段對(duì)話:司令:你猜我買的這個(gè)多少錢？
我: 1000
司令: 高了
我: 500
司令: 低了:
我: 750
...... 直到最后猜中
這樣說(shuō)大家應(yīng)該已經(jīng)猜到了是「二分查找法」，通過(guò)這個(gè)例子我想要引出的是 樹(shù)，來(lái)看圖片
程序中的樹(shù)其實(shí)是我們?nèi)粘？吹降臉?shù)的倒影，或者發(fā)揮一下想象，倒影也可以是樹(shù)根
二叉查找樹(shù)，Binary Search Tree 「BST」，要想了解二叉查找樹(shù)，我們首先看下二叉查找樹(shù)有哪些特性呢？
某節(jié)點(diǎn)的左子樹(shù)節(jié)點(diǎn)值僅包含小于該節(jié)點(diǎn)值
某節(jié)點(diǎn)的右子樹(shù)節(jié)點(diǎn)值僅包含大于該節(jié)點(diǎn)值
左右子樹(shù)每個(gè)也必須是二叉查找樹(shù)
看個(gè)圖就輕松理解上面三句話的意思了:
上圖，結(jié)合二叉查找樹(shù)的三條約束來(lái)看，非常好，沒(méi)有什么問(wèn)題。再來(lái)看一個(gè)圖，依舊符合上面三條約束，感覺(jué)有問(wèn)題嗎？
這是一個(gè)走路一米六，一米八的樹(shù)
這是一個(gè)畸形的樹(shù)，大風(fēng)一掛很可能被折斷的樹(shù)
從程序的角度來(lái)說(shuō)這個(gè)樹(shù)不夠平衡，查找次數(shù)或時(shí)間復(fù)雜度 O(h)可能會(huì)隨著一條腿長(zhǎng)無(wú)限增長(zhǎng)
理科生在高中學(xué)習(xí)生物時(shí)學(xué)過(guò)一個(gè)關(guān)鍵字「去除頂端優(yōu)勢(shì)」，通過(guò)去除植物頂端優(yōu)勢(shì)，側(cè)芽會(huì)迅速生長(zhǎng)，慢慢變得強(qiáng)壯和平衡， 紅黑樹(shù)其實(shí)就是去除二叉查找樹(shù)頂端優(yōu)勢(shì)的解決方案，從而達(dá)到樹(shù)的平衡
紅黑樹(shù)紅黑樹(shù)，Red-Black Tree 「RBT」是一個(gè)自平衡(不是絕對(duì)的平衡)的二叉查找樹(shù)(BST)，樹(shù)上的每個(gè)節(jié)點(diǎn)都遵循下面的規(guī)則:
每個(gè)節(jié)點(diǎn)都有紅色或黑色
樹(shù)的根始終是黑色的 (黑土地孕育黑樹(shù)根，
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/77911.html
摘要：在項(xiàng)目中，為滿足以上要求，我們將大量的參數(shù)配置在或文件中，通過(guò)注解，我們可以方便的獲取這些參數(shù)值使用配置模塊假設(shè)我們正在搭建一個(gè)發(fā)送郵件的模塊。這使得在不影響其他模塊的情況下重構(gòu)一個(gè)模塊中的屬性變得容易。 在編寫項(xiàng)目代碼時(shí)，我們要求更靈活的配置，更好的模塊化整合。在 Spring Boot 項(xiàng)目中，為滿足以上要求，我們將大量的參數(shù)配置在 application.properties 或...
摘要：在項(xiàng)目中，為滿足以上要求，我們將大量的參數(shù)配置在或文件中，通過(guò)注解，我們可以方便的獲取這些參數(shù)值使用配置模塊假設(shè)我們正在搭建一個(gè)發(fā)送郵件的模塊。這使得在不影響其他模塊的情況下重構(gòu)一個(gè)模塊中的屬性變得容易。 在編寫項(xiàng)目代碼時(shí)，我們要求更靈活的配置，更好的模塊化整合。在 Spring Boot 項(xiàng)目中，為滿足以上要求，我們將大量的參數(shù)配置在 application.properties 或...
面試舊敵之紅黑樹(shù)（直白介紹深入理解） - Android - 掘金 讀完本文你將了解到： 什么是紅黑樹(shù) 黑色高度 紅黑樹(shù)的 5 個(gè)特性 紅黑樹(shù)的左旋右旋 指定節(jié)點(diǎn) x 的左旋 右圖轉(zhuǎn)成左圖 指定節(jié)點(diǎn) y 的右旋左圖轉(zhuǎn)成右圖 紅黑樹(shù)的平衡插入 二叉查找樹(shù)的插入 插入后調(diào)整紅黑樹(shù)結(jié)構(gòu) 調(diào)整思想 插入染紅后... java 多線程同步以及線程間通信詳解 & 消費(fèi)者生產(chǎn)者模式 & 死鎖 & Thread...
摘要：算法導(dǎo)論由于性質(zhì)，紅黑樹(shù)中不會(huì)出現(xiàn)兩個(gè)紅色結(jié)點(diǎn)相鄰的情形。紅黑樹(shù)的插入首先以二叉搜索樹(shù)的方式插入結(jié)點(diǎn)，并將其著為紅色。假設(shè)整棵二叉搜索樹(shù)中，只有和因違背性質(zhì)而無(wú)法成為正常的紅黑樹(shù)，此時(shí)將圖調(diào)整成圖，則可以恢復(fù)成正常的紅黑樹(shù)。 紅黑樹(shù)的性質(zhì) 一棵滿足以下性質(zhì)的二叉搜索樹(shù)是一棵紅黑樹(shù) 每個(gè)結(jié)點(diǎn)或是黑色或是紅色。 根結(jié)點(diǎn)是黑色的。 每個(gè)葉結(jié)點(diǎn)(NIL)是黑色的。 如果一個(gè)結(jié)點(diǎn)是紅色的，則它...
閱讀 1478·2021-11-18 10:02
閱讀 1625·2021-09-04 16:40
閱讀 3150·2021-09-01 10:48
閱讀 852·2019-08-30 15:55
閱讀 1831·2019-08-30 15:55
閱讀 1346·2019-08-30 13:05
閱讀 2997·2019-08-30 12:52
閱讀 1598·2019-08-30 11:24
