国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

紅黑樹的插入

sunsmell / 3322人閱讀

摘要:算法導(dǎo)論由于性質(zhì),紅黑樹中不會(huì)出現(xiàn)兩個(gè)紅色結(jié)點(diǎn)相鄰的情形。紅黑樹的插入首先以二叉搜索樹的方式插入結(jié)點(diǎn),并將其著為紅色。假設(shè)整棵二叉搜索樹中,只有和因違背性質(zhì)而無法成為正常的紅黑樹,此時(shí)將圖調(diào)整成圖,則可以恢復(fù)成正常的紅黑樹。

紅黑樹的性質(zhì)

一棵滿足以下性質(zhì)的二叉搜索樹是一棵紅黑樹

每個(gè)結(jié)點(diǎn)或是黑色或是紅色。

根結(jié)點(diǎn)是黑色的。

每個(gè)葉結(jié)點(diǎn)(NIL)是黑色的。

如果一個(gè)結(jié)點(diǎn)是紅色的,則它的兩個(gè)子結(jié)點(diǎn)都是黑色的。

對(duì)每個(gè)結(jié)點(diǎn),從該結(jié)點(diǎn)到其所有后代葉結(jié)點(diǎn)的簡單路徑上,均包含相同數(shù)目的黑色結(jié)點(diǎn)。

性質(zhì)1和性質(zhì)2,不用做過多解釋。

性質(zhì)3,每個(gè)葉結(jié)點(diǎn)(NIL)是黑色的。這里的葉結(jié)點(diǎn)并不是指上圖中結(jié)點(diǎn)1,5,8,15,而是指下圖中值為null的結(jié)點(diǎn),它們的顏色為黑色,且是它們父結(jié)點(diǎn)的子結(jié)點(diǎn)。

性質(zhì)4,如果一個(gè)結(jié)點(diǎn)是紅色的(圖中用白色代替紅色),則它的兩個(gè)子結(jié)點(diǎn)都是黑色的,例如結(jié)點(diǎn)2,5,8,15。但是,如果某結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)都是黑色的,該結(jié)點(diǎn)未必是紅色的,例如結(jié)點(diǎn)1

性質(zhì)5,對(duì)每個(gè)結(jié)點(diǎn),從該結(jié)點(diǎn)到其所有后代葉結(jié)點(diǎn)的簡單路徑上,均包含相同數(shù)目的黑色結(jié)點(diǎn)。例如,從結(jié)點(diǎn)2到其所有后代葉結(jié)點(diǎn)的簡單路徑上,黑色結(jié)點(diǎn)的數(shù)量都為2;從根結(jié)點(diǎn)11到其所有后代葉結(jié)點(diǎn)的簡單路徑上,黑色結(jié)點(diǎn)的數(shù)量都為3。

這樣的一棵樹有什么特點(diǎn)呢?

通過對(duì)任何一條從根到葉結(jié)點(diǎn)的簡單路徑上各個(gè)結(jié)點(diǎn)的顏色進(jìn)行約束,紅黑樹確保沒有一條路徑會(huì)比其他路徑長出2倍,因?yàn)槭墙朴谄胶獾摹!端惴▽?dǎo)論》

由于性質(zhì)4,紅黑樹中不會(huì)出現(xiàn)兩個(gè)紅色結(jié)點(diǎn)相鄰的情形。樹中最短的可能出現(xiàn)的路徑是都是黑色結(jié)點(diǎn)的路徑,樹中最長的可能出現(xiàn)的路徑是紅色結(jié)點(diǎn)和黑色結(jié)點(diǎn)交替的路徑。再結(jié)合性質(zhì)5,每條路徑上均包含相同數(shù)目的黑色結(jié)點(diǎn),所以紅黑樹確保沒有一條路徑會(huì)比其他路徑長出2倍

紅黑樹的插入

首先以二叉搜索樹的方式插入結(jié)點(diǎn),并將其著為紅色。如果著為黑色,則會(huì)違背性質(zhì)5,不便調(diào)整;如果著為紅色,可能會(huì)違背性質(zhì)2或性質(zhì)4,可以通過相對(duì)簡單的操作,使其恢復(fù)紅黑樹的性質(zhì)。

一個(gè)結(jié)點(diǎn)以二叉搜索樹的方式被插入后,可能出現(xiàn)以下幾種情況:

情形1

插入結(jié)點(diǎn)后,無父結(jié)點(diǎn),結(jié)點(diǎn)插入成為根結(jié)點(diǎn),違背性質(zhì)2,將結(jié)點(diǎn)調(diào)整為黑色,完成插入。

情形2

插入結(jié)點(diǎn)后,其父結(jié)點(diǎn)為黑色,沒有違背任何性質(zhì),不用調(diào)整,完成插入。例如下圖中插入結(jié)點(diǎn)13

情形3

插入結(jié)點(diǎn)后,其父結(jié)點(diǎn)為紅色,違背了性質(zhì)4,需要采取一系列的調(diào)整。例如下圖中插入結(jié)點(diǎn)4

那么一系列的調(diào)整是什么呢?

如果插入結(jié)點(diǎn)node的父結(jié)點(diǎn)father為紅色,則結(jié)點(diǎn)father必然存在黑色的父結(jié)點(diǎn)grandfather,因?yàn)槿绻Y(jié)點(diǎn)father不存在父結(jié)點(diǎn)的話,就是根結(jié)點(diǎn),而根結(jié)點(diǎn)是黑色的。那么結(jié)點(diǎn)grandfather的另一個(gè)子結(jié)點(diǎn),我們可以稱之為結(jié)點(diǎn)uncle,即結(jié)點(diǎn)father的兄弟結(jié)點(diǎn)。結(jié)點(diǎn)uncle可能為黑色,也可能為紅色。

先從最簡單的情形分析,因?yàn)閺?fù)雜的情形可以轉(zhuǎn)化為簡單的情形,簡單的情形就是結(jié)點(diǎn)uncle為黑色的情形。

情形3.1

如上圖(a)中,情形是這樣的,node 為紅,father 為紅,grandfatheruncle 為黑,α,β,θ,ω,η 都是結(jié)點(diǎn)對(duì)應(yīng)的子樹。假設(shè)整棵二叉搜索樹中,只有nodefather因違背性質(zhì)4而無法成為正常的紅黑樹,此時(shí)將圖(a)調(diào)整成圖(b),則可以恢復(fù)成正常的紅黑樹。整個(gè)調(diào)整過程中實(shí)際分為兩步,旋轉(zhuǎn)變色

什么是旋轉(zhuǎn)?

如上圖(c)是一棵二叉搜索樹的一部分,其中 x, y 是結(jié)點(diǎn),α,β,θ 是對(duì)應(yīng)結(jié)點(diǎn)的子樹。由圖可知,α < x < β < y < θ ,即 α子樹中的所有結(jié)點(diǎn)都小于x,結(jié)點(diǎn) x都小于 β子樹中的所有結(jié)點(diǎn),β子樹中的所有結(jié)點(diǎn)的值都小于結(jié)點(diǎn) y 的值,結(jié)點(diǎn) y 的值都小于 θ子樹中的所有結(jié)點(diǎn)。在二叉搜索樹中,如果結(jié)點(diǎn)y的值比結(jié)點(diǎn)x的值大,那么結(jié)點(diǎn)x在結(jié)點(diǎn)y的左子樹中,如圖(c);或者結(jié)點(diǎn)y在結(jié)點(diǎn)x的右子樹中,如圖(d)。故 α < x < β < y < θ ,也可以用圖(d)的結(jié)構(gòu)來表現(xiàn)。這就是旋轉(zhuǎn),它不會(huì)破壞二叉搜索樹的性質(zhì)。

node 為紅,father 為紅,grandfatheruncle 為黑的具體情形一

圖(a)中,nodefather 的左子結(jié)點(diǎn), fathergrand 的左子結(jié)點(diǎn),node < father < θ < grand < uncle。這種情形中 father < grand,即可以表現(xiàn)為 father 是 grand 的左子樹,也可以表現(xiàn)為 grand 是 father 的右子樹,故將圖(a)中 father 和 grand 旋轉(zhuǎn),旋轉(zhuǎn)雖然不會(huì)破壞二叉搜索樹的性質(zhì),但是旋轉(zhuǎn)之后,會(huì)破壞紅黑樹的性質(zhì),所以還需要調(diào)整結(jié)點(diǎn)的顏色。

變色

所以圖(a)旋轉(zhuǎn)過后,還要將 grand 變?yōu)榧t色,father 變?yōu)楹谏兂蓤D(b),完成插入。

node 為紅,father 為紅,grandfatheruncle 為黑的具體情形二

nodefather 的右子結(jié)點(diǎn), fathergrand 的右子結(jié)點(diǎn),如下圖(e),就是具體情形一的翻轉(zhuǎn)。

即,uncle < grand < θ < father < node ,將圖(e)中 father 和 grand 旋轉(zhuǎn)變色后,變成圖(f),完成插入。

node 為紅,father 為紅,grandfatheruncle 為黑的具體情形三

nodefather 的右子結(jié)點(diǎn), fathergrand 的左子結(jié)點(diǎn),如下圖(m)。

將圖(m)中 node 和 father 旋轉(zhuǎn)后,變成圖(n),將father看作新的node,就成為了具體情形一,再次旋轉(zhuǎn)變色后,完成插入。

node 為紅,father 為紅,grandfatheruncle 為黑的具體情形四

nodefather 的右子結(jié)點(diǎn), fathergrand 的左子結(jié)點(diǎn),如下圖(i),就是具體情形三的翻轉(zhuǎn)。

將圖(i)中 node 和 father 旋轉(zhuǎn)后,變成圖(j),將father看作新的node,就成為了具體情形二,再次旋轉(zhuǎn)變色后,完成插入。

情形3.2

nodefatheruncle 為紅,grandfather 為黑

如上圖(k),不旋轉(zhuǎn),而是將grand著紅,father和uncle著黑,同時(shí)將grand作為新的node,進(jìn)行情形的判斷。如果grand作為新的node后,變成了情形2,則插入完成;如果變成了情形3.1,則調(diào)整后,插入完成;如果仍是情形3.2,則繼續(xù)將grand,father和uncle變色,和node結(jié)點(diǎn)上移,如果新的node結(jié)點(diǎn)沒有父節(jié)點(diǎn)了,則變成了情形1,將根結(jié)點(diǎn)著為黑色,那么插入完成。

綜上
node的情形 操作
情形1 node為紅,無father 將node重新著色
情形2 node為紅,father為黑
情形3.1 node,father為紅,grand,uncle為黑 旋轉(zhuǎn)一次或兩次,并重新著色
情形3.2 node,father,uncle為紅,grand為黑 將father, uncle,grand重新著色, grand作為新的node
代碼
// 結(jié)點(diǎn)
function Node(value) {
  this.value = value
  this.color = "red" // 結(jié)點(diǎn)的顏色默認(rèn)為紅色
  this.parent = null
  this.left = null
  this.right = null
}

function RedBlackTree() {
  this.root = null
}

RedBlackTree.prototype.insert = function (node) {
  // 以二叉搜索樹的方式插入結(jié)點(diǎn)
  // 如果根結(jié)點(diǎn)不存在,則結(jié)點(diǎn)作為根結(jié)點(diǎn)
  // 如果結(jié)點(diǎn)的值小于node,且結(jié)點(diǎn)的右子結(jié)點(diǎn)不存在,跳出循環(huán)
  // 如果結(jié)點(diǎn)的值大于等于node,且結(jié)點(diǎn)的左子結(jié)點(diǎn)不存在,跳出循環(huán)
  if (!this.root) {
    this.root = node
  } else {
    let current = this.root
    while (current[node.value <= current.value ? "left" : "right"]) {
      current = current[node.value <= current.value ? "left" : "right"]
    }
    current[node.value <= current.value ? "left" : "right"] = node
    node.parent = current
  }
  // 判斷情形
  this._fixTree(node)
  return this
}

RedBlackTree.prototype._fixTree = function (node) {
  // 當(dāng)node.parent不存在時(shí),即為情形1,跳出循環(huán)
  // 當(dāng)node.parent.color === "black"時(shí),即為情形2,跳出循環(huán)
  while (node.parent && node.parent.color !== "black") {
    // 情形3
    let father = node.parent
    let grand = father.parent
    let uncle = grand[grand.left === father ? "right" : "left"]
    if (!uncle || uncle.color === "black") {
      // 葉結(jié)點(diǎn)也是黑色的
      // 情形3.1
      let directionFromFatherToNode = father.left === node ? "left" : "right"
      let directionFromGrandToFather = grand.left === father ? "left" : "right"
      if (directionFromFatherToNode === directionFromGrandToFather) {
        // 具體情形一或二
        // 旋轉(zhuǎn)
        this._rotate(father)
        // 變色
        father.color = "black"
        grand.color = "red"
      } else {
        // 具體情形三或四
        // 旋轉(zhuǎn)
        this._rotate(node)
        this._rotate(node)
        // 變色
        node.color = "black"
        grand.color = "red"
      }
      break // 完成插入,跳出循環(huán)
    } else {
      // 情形3.2
      // 變色
      grand.color = "red"
      father.color = "black"
      uncle.color = "black"
      // 將grand設(shè)為新的node
      node = grand
    }
  }

  if (!node.parent) {
    // 如果是情形1
    node.color = "black"
    this.root = node
  }
}

RedBlackTree.prototype._rotate = function (node) {
  // 旋轉(zhuǎn) node 和 node.parent
  let y = node.parent
  if (y.right === node) {
    if (y.parent) {
      y.parent[y.parent.left === y ? "left" : "right"] = node
    }
    node.parent = y.parent
    if (node.left) {
      node.left.parent = y
    }
    y.right = node.left
    node.left = y
    y.parent = node
  } else {
    if (y.parent) {
      y.parent[y.parent.left === y ? "left" : "right"] = node
    }
    node.parent = y.parent
    if (node.right) {
      node.right.parent = y
    }
    y.left = node.right
    node.right = y
    y.parent = node
  }
}

let arr = [11, 2, 14, 1, 7, 15, 5, 8, 4, 16]
let tree = new RedBlackTree()
arr.forEach(i => tree.insert(new Node(i)))
debugger

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/89928.html

相關(guān)文章

  • 數(shù)據(jù)結(jié)構(gòu)與算法(十四)深入理解黑樹和JDK TreeMap和TreeSet源碼分析

    摘要:很多文章或書籍在介紹紅黑樹的時(shí)候直接上來就是紅黑樹的個(gè)基本性質(zhì)插入刪除操作等。這也不奇怪,算法的作者就是紅黑樹的作者之一。所以,理解樹對(duì)掌握紅黑樹是至關(guān)重要的。 本文主要包括以下內(nèi)容: 什么是2-3樹 2-3樹的插入操作 紅黑樹與2-3樹的等價(jià)關(guān)系 《算法4》和《算法導(dǎo)論》上關(guān)于紅黑樹的差異 紅黑樹的5條基本性質(zhì)的分析 紅黑樹與2-3-4樹的等價(jià)關(guān)系 紅黑樹的插入、刪除操作 JDK ...

    curlyCheng 評(píng)論0 收藏0
  • JDK源碼那些事兒之黑樹基礎(chǔ)上篇

    摘要:用這種范例表示紅黑樹是可能的,但是這會(huì)改變一些性質(zhì)并使算法復(fù)雜。插入會(huì)出現(xiàn)種情況為根節(jié)點(diǎn),即紅黑樹的根節(jié)點(diǎn)。 說到HashMap,就一定要說到紅黑樹,紅黑樹作為一種自平衡二叉查找樹,是一種用途較廣的數(shù)據(jù)結(jié)構(gòu),在jdk1.8中使用紅黑樹提升HashMap的性能,今天就來說一說紅黑樹。 前言 限于篇幅,本文只對(duì)紅黑樹的基礎(chǔ)進(jìn)行說明,暫不涉及源碼部分,大部分摘抄自維基百科,這里也貼出對(duì)應(yīng)鏈接...

    qylost 評(píng)論0 收藏0
  • 樹 - (二叉查找樹,黑樹,B樹)- 黑樹

    摘要:需要執(zhí)行的操作依次是首先,將紅黑樹當(dāng)作一顆二叉查找樹,將該節(jié)點(diǎn)從二叉查找樹中刪除然后,通過旋轉(zhuǎn)和重新著色等一系列來修正該樹,使之重新成為一棵紅黑樹。 雖是讀書筆記,但是如轉(zhuǎn)載請(qǐng)注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復(fù)制黨 關(guān)于二叉樹的基本知識(shí),可以參見:Java 實(shí)現(xiàn)基本數(shù)據(jù)結(jié)構(gòu) 2(樹) 以下是算法導(dǎo)論第13章的學(xué)...

    yangrd 評(píng)論0 收藏0
  • 集合框架知識(shí)系列06 HashMap和TreeMap中的黑樹

    摘要:在上一節(jié)中,在中用了鏈表和紅黑樹兩種方式解決沖突,在中也是用紅黑樹存儲(chǔ)的。其中節(jié)點(diǎn)顏色為黑色紅黑樹的左旋和右旋紅黑樹的插入和刪除,都有可能破壞其特性,就不是一棵紅黑樹了,所以要調(diào)整。 在上一節(jié)中,HashMap在jdk 1.8中用了鏈表和紅黑樹兩種方式解決沖突,在TreeMap中也是用紅黑樹存儲(chǔ)的。下面分析一下紅黑樹的結(jié)構(gòu)和基本操作。 一、紅黑樹的特征和基本操作 上一節(jié)中已經(jīng)描述了紅黑...

    李增田 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<