忍者ブログ
  • 2019.09
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 2019.11
赤黒木をgoで実装してみた
作ったのはこちら
https://github.com/doshiraki/rbtree_bygo/blob/master/rbtree.go


赤黒木

やっぱり削除は難しい。。。
ポイントは、delete case 3,4がまったく同じ結果というようにまとめられること。
	Node := delNode
	for {
		parent := Node.parent
		if parent == nil {
			//case 1
			break
		}

		dir := Node.dir()
		dirOther := dir ^ 1
		sibling := parent.children[dirOther]

		if sibling.isRed {
			//case 2
			parent.flip(dirOther)
			sibling.isRed = false
			parent.isRed = true
			sibling = parent.children[dirOther]
		}
		//sibling is Black

		nephew := sibling.children[dirOther]
		if nephew == nil || !nephew.isRed {
			//far nephew is Black
			nephew = sibling.children[dir]
			if nephew == nil || !nephew.isRed {
				//near nephew is Black
				sibling.isRed = true
				if parent.isRed {
					//case 4
					parent.isRed = false
					break
				} else {
					//case 3
					Node = parent
					continue
				}
			}
			//case 5
			//near nephew is Red and far nephew is Black
			sibling.flip(dir)
			sibling, nephew = nephew, sibling
			sibling.isRed = false
			nephew.isRed = true
		}
		//case 6
		//sibling is Black && far nephew is Red

		saveColor := parent.isRed
		parent.flip(dirOther)
		sibling.isRed = saveColor
		parent.isRed = false
		nephew.isRed = false
		break

	}

PR
【2019/09/23 10:24 】 | go | 有り難いご意見(3)
                                    
| ホーム |