从2-4树到红黑树

2023-04-30
9分钟阅读时长
Data Structure

对于一般的二叉搜索树来说，查找、插入、删除的平均时间复杂度都是$O(logN)$，但最坏情况是$O(N)$。而平衡树可以保证这三种方法的复杂度都是$O(logN)$，平衡树通过重构使得树的高度是平衡的，不会退化成单链。红黑树就是平衡树的一种。

本文将先介绍2-3-4树，通过2-3-4树引入到红黑树。

2-3-4树

2-3-4树也叫2-4树，是一种自平衡的数据结构。之所以这么叫是因为2-4树的节点类型有以下三种

  • 2-node：存储一个key，有两个儿子节点
  • 3-node：存储两个key，有三个儿子节点
  • 4-node：存储三个key，有四个儿子节点

2-4树是4阶B树，查找、插入、删除的时间复杂度都是$O(logN)$。2-4树有一个重要的性质就是每一个叶子节点的深度都是相同的。

2-4tree

2-4 Tree

对于2-node来说，左儿子表示的范围是$(-\infty, v)$，右儿子表示的范围是$(v, +\infty)$，其他类型的节点也是同理。

为什么是2-3-4

为什么不最大化儿子节点的数量来让树的高度最小？假设所有节点都是d-node的话，查询的时间复杂度会更低吗？

假设$d = N^{1/2}$，意味着树的高度是2，那么我们在每一层通过二分查找查询正确节点的时间复杂度是$O(logN^{1/2})$，而$2logN^{1/2} = O(logN)$，并没有得到优化。2-3-4树会保证树的高度在$O(logN)$。

插入

对于2-node和3-node，都是直接插入即可。

ins2-3node

insert 2 node & 3 node

对于4-node的插入则要麻烦一些。因为4-node已经没法直接存入值了。首先需要将中间值提取出来，存储到父节点中，剩下的左值和右值以及4个儿子节点分裂成两个2-node挂在父节点下，然后再根据上面的情况插入新值即可。

ins4-node

insert 4 node

假如该4-node的父节点也是4-node节点怎么办？继续向上分裂即可。

删除

2-3-4树删除节点分比较多种情况。

  1. 如果k是在叶子结点，并且该叶子节点至少存储了两个key，则直接删除即可

  2. 如果k是在当前节点内，则执行以下三种操作之一

    1. 如果左儿子至少有两个key，则用值最大的key替换掉k，并删除左儿子中最大的key
    2. 如果右儿子至少有两个key，则用值最小的key替换掉k，并删除右儿子中最小的key
    3. 如果左右儿子都只有一个key，则将左儿子、右儿子和k合并成4-node，并从原节点删除k，新的4-node节点为原节点的左儿子，然后从4-node节点中删除k即可

  3. 如果k不在当前节点内，则根据正确的路径找到向下找。在这个过程中，需要保证经过的节点都至少包含两个key，因此过程中可能需要执行以下两种操作之一

    1. 如果即将去到的节点仅有一个key，并且兄弟节点至少有两个key，则从当前节点移动一个key到目标路径节点，从兄弟节点移动一个key到当前节点。
    2. 如果即将去到的节点仅有一个key，并且兄弟节点也只有一个key，则和当前节点的一个key进行合并成一个4-node，并且这个值在中间。

case1

case2a

case2b

case2c

case3a

case3b

Red Black Tree

红黑树和2-4树是等价的，任何一颗2-4树都可以转换成红黑树。红黑树是二叉搜索树，只有2-node节点。每个节点要么是黑色，要么是红色，通过颜色可以表示2-4树中的3-node和4-node。

2-4tree2rbt

2-4 tree to rbt

红黑树的高度最多会是2-4树的两倍，例如下面这个case，整体的高度还是$O(logN)$

2h

性质

  1. 从root到leaf的路径上不会有连续的红色节点，即父节点和儿子节点不会都是红色（red property）
  2. 从root到所有leaf的路径上，黑色节点的数量是相同的（black property）
  3. root节点永远都是黑色（root property）
  4. 每一个NIL节点可以看作是黑色节点，black property需要计算上黑色NIL节点的数量

插入

插入操作是将值k插入到红黑树中，并且维持红黑树的性质。如果是一颗空树的话，则生成一个黑节点，存储k即可。若是一颗非空树，则需要执行以下操作：

  1. 找到合适的叶子结点位置
  2. 将k插入到该叶子结点的位置，并且为红色节点
  3. 必要时候通过旋转、变色操作来维护红黑树性质。

现在来分析一下插入到非空树的情况，假设我们要插入的节点为k，父节点为p，祖父节点为g。

  • Case1：p是黑节点

如果k的父节点p是黑节点，那么直接插入即可，什么也不需要调整，性质都不会被破坏。从2-4树来看，就是2-node变成3-node的过程。

  • Case2：p是红节点

如果k的父节点p是红节点，则出现了double-red的情况，破坏了red property，此时p的父节点g（k的祖父节点）为黑节点，为了解除double-red的情况，我们需要考虑g的另一个儿子节点s（即p的兄弟节点）的颜色。

  • Case2a：s是黑节点或nil

如果s是黑节点或者nil，则我们需要将k、p和g这三个节点重组。首先按照k、p、g三个节点的值进行从小到大的排序，假设排序结果是a、b、c，则将a和c设置为b的儿子节点，涂为红色，b为黑节点，同时考虑p的子树以及s是在合适的位置。

rbt-ins-black

rbt insert Case 2a
  • Case2b：s是红节点

如果s是红节点，则将p和s的颜色改变成黑色，g节点的颜色改成红色（如果g节点是root则保持黑色不变）。由于g节点变成了红色，g和g的父节点可能出现double-red的情况，则根据case2a的方法调整即可。

rbt-ins-red

rbt insert Case 2b

删除

删除操作是从红黑树中找到要删除的节点x，将节点移除的过程。删除操作和插入操作一样可能会破坏红黑树的性质，删除后通过旋转和变色操作修复破坏的性质。

二叉搜索树的删除，通常不是直接删除节点本身，而是找到前驱或者后继节点，将值替换到原本要删除的节点，然后将问题转换成删除前驱或者后继节点。且前驱和后继节点只多只有一个子节点。

  • 当前是红色节点

    • 是红色叶子节点则直接删除即可，不影响任何性质

    • 有一个子节点（不可能的情况）

      • 有一个红色子节点，出现double-red情况
      • 有一个黑色子节点，破坏了black property性质

  • 当前是黑色节点

    • 是黑色叶子节点，这是最复杂的情况，下面会详细讨论

      • Case1：兄弟节点是红色的
      • Case2：兄弟节点是黑色的且有两个黑色节点儿子
      • Case3：兄弟节点是黑色的且兄弟节点左儿子是红色，右儿子是黑色的
      • Case4：兄弟节点是黑色的且兄弟节点右儿子是红色的

    • 有一个黑色子节点（不可能的情况）

      • 破坏了black property性质

    • 有一个红色子节点

      • 将这个红色子节点替换自己的位置，并且变色成黑色即可
rbt deletion
  • Case1：当前是黑色叶子节点，且兄弟节点是红色的

首先将父节点和兄弟节点的颜色变换一下，然后父节点相对于兄弟节点进行旋转操作。当前仍然没有完全恢复红黑树的性质，但是转换成了Case2或Case3的情况，将根据Case2或者Case3的操作继续恢复。

rbt-del-case1

  • Case2： 当前是黑色叶子节点，兄弟节点是黑色且有两个黑色儿子

首先将sibling变色成红色，然后将current移动到parent节点，这时候会有两种情况，parent是红色的或者是黑色的。如果parent是红色的，则变色成黑色即可结束。否则根据情况继续修复。

del-case2

  • Case3：兄弟节点是黑色的且兄弟节点左儿子是红色，右儿子是黑色的

将兄弟节点的左儿子变色成黑色，兄弟节点变色成红色，对兄弟节点进行右旋，并用case4的方法继续修复。

del-case3

  • Case4：兄弟节点是黑色的且兄弟节点右儿子是红色的

将sibling变色成parent的颜色，将parent变成黑色，将sibling的右儿子变成黑色，对parent进行左旋，将current移至root并且变色成黑色。

del-case4

代码

Red Black Tree implemented by Go

type Color byte

const (
	Red Color = iota
	Black
)

type Direction byte

const (
	DirRoot Direction = iota
	DirLeft
	DirRight
)

type RBNode[T constraints.Ordered] struct {
	Val    T
	parent *RBNode[T]
	left   *RBNode[T]
	right  *RBNode[T]
	color  Color
}

func newRBNode[T constraints.Ordered](v T) *RBNode[T] {
	return &RBNode[T]{
		Val:    v,
		parent: nil,
		left:   nil,
		right:  nil,
		color:  Red,
	}
}

func (n *RBNode[T]) isLeaf() bool {
	return (n.left == nil && n.right == nil)
}

func (n *RBNode[T]) isRoot() bool {
	return n.parent == nil
}

func (n *RBNode[T]) isRed() bool {
	return n.color == Red
}

func (n *RBNode[T]) isBlack() bool {
	return n.color == Black
}

func (n *RBNode[T]) direction() Direction {
	if n.parent != nil {
		if n == n.parent.left {
			return DirLeft
		} else {
			return DirRight
		}
	} else {
		return DirRoot
	}
}

func (n *RBNode[T]) sibling() *RBNode[T] {
	if n.direction() == DirLeft {
		return n.parent.right
	} else {
		return n.parent.left
	}
}

func (n *RBNode[T]) hasSibling() bool {
	return (!n.isRoot() && n.sibling() != nil)
}

func (n *RBNode[T]) uncle() *RBNode[T] {
	return n.parent.sibling()
}

func (n *RBNode[T]) hasUncle() bool {
	return (!n.isRoot() && n.parent.hasSibling())
}

func (n *RBNode[T]) grandParent() *RBNode[T] {
	return n.parent.parent
}

func (n *RBNode[T]) hasGrandParent() bool {
	return (!n.isRoot() && !n.parent.isRoot())
}

func (n *RBNode[T]) release() {
	n.parent = nil
	if n.left != nil {
		n.left.release()
	}
	if n.right != nil {
		n.right.release()
	}
}

type RBTree[T constraints.Ordered] struct {
	root *RBNode[T]
	cnt  uint
}

func NewRBTree[T constraints.Ordered]() *RBTree[T] {
	return &RBTree[T]{
		root: nil,
		cnt:  0,
	}
}

func (t *RBTree[T]) Size() uint {
	return t.cnt
}

func (t *RBTree[T]) Empty() bool {
	return t.cnt == 0
}

func (t *RBTree[T]) Clear() {
	if t.root != nil {
		t.root.release()
		t.root = nil
	}
	t.cnt = 0
}

func search[T constraints.Ordered](n *RBNode[T], v T) (*RBNode[T], bool) {
	if n == nil {
		return nil, false
	}

	if n.Val == v {
		return n, true
	}
	if n.Val < v {
		return search(n.right, v)
	}
	return search(n.left, v)
}

func (t *RBTree[T]) Get(v T) (*RBNode[T], bool) {
	return search(t.root, v)
}

func (t *RBTree[T]) Has(v T) bool {
	_, ok := search(t.root, v)
	return ok
}

func (t *RBTree[T]) Insert(v T) {
	if t.root == nil {
		t.root = newRBNode(v)
		t.root.color = Black
		t.cnt++
	} else {
		t.insert(t.root, v)
	}
}

func (n *RBNode[T]) maintainRelationship() {
	if n.left != nil {
		n.left.parent = n
	}
	if n.right != nil {
		n.right.parent = n
	}
}

func (t *RBTree[T]) leftRotate(n *RBNode[T]) {
	if n == nil || n.right == nil {
		return
	}

	parent := n.parent
	dir := n.direction()

	successor := n.right
	n.right = successor.left
	successor.left = n

	n.maintainRelationship()
	successor.maintainRelationship()

	switch dir {
	case DirRoot:
		t.root = successor
		break
	case DirLeft:
		parent.left = successor
		break
	case DirRight:
		parent.right = successor
		break
	}

	successor.parent = parent
}

func (t *RBTree[T]) rightRotate(n *RBNode[T]) {
	if n == nil || n.left == nil {
		return
	}

	parent := n.parent
	dir := n.direction()

	successor := n.left
	n.left = successor.right
	successor.right = n

	n.maintainRelationship()
	successor.maintainRelationship()

	switch dir {
	case DirRoot:
		t.root = successor
		break
	case DirLeft:
		parent.left = successor
		break
	case DirRight:
		parent.right = successor
		break
	}

	successor.parent = parent
}

func (t *RBTree[T]) insert(n *RBNode[T], v T) {
	if n.Val == v {
		return
	}

	if v < n.Val {
		if n.left == nil {
			n.left = newRBNode(v)
			n.left.parent = n
			t.insertFixUp(n.left)
			t.cnt++
		} else {
			t.insert(n.left, v)
		}
	} else {
		if n.right == nil {
			n.right = newRBNode(v)
			n.right.parent = n
			t.insertFixUp(n.right)
			t.cnt++
		} else {
			t.insert(n.right, v)
		}
	}
}

func (t *RBTree[T]) insertFixUp(n *RBNode[T]) {
	if n.isRoot() {
		n.color = Black
		return
	}

	if n.parent.isBlack() {
		// case 1: parent is black
		return
	}

	if n.parent.isRoot() {
		n.parent.color = Black
		return
	}

	if !n.hasUncle() || n.uncle().isBlack() {
		// case 2a: uncle is nil or black
		if n.direction() != n.parent.direction() {
			parent := n.parent
			if n.direction() == DirLeft {
				t.rightRotate(n.parent)
			} else {
				t.leftRotate(n.parent)
			}
			n = parent
		}

		if n.parent.direction() == DirLeft {
			t.rightRotate(n.grandParent())
		} else {
			t.leftRotate(n.grandParent())
		}

		n.parent.color = Black
		n.sibling().color = Red
		return
	}

	if n.hasUncle() && n.uncle().isRed() {
		// case 2b: uncle is red
		n.parent.color = Black
		n.uncle().color = Black
		n.grandParent().color = Red
		t.insertFixUp(n.grandParent())
		return
	}
}

func (t *RBTree[T]) Delete(v T) {
	if t.root == nil {
		return
	} else {
		t.delete(t.root, v)
	}
}

func (t *RBTree[T]) delete(n *RBNode[T], v T) {
	if n == nil {
		return
	}

	if n.Val != v {
		if v < n.Val {
			left := n.left
			t.delete(left, v)
		} else {
			right := n.right
			t.delete(right, v)
		}
		n.maintainRelationship()
		return
	}

	// only root
	if t.Size() == 1 {
		t.Clear()
		return
	}

	if n.left != nil && n.right != nil {
		successor := n.right
		parent := n
		// find successor of current
		for successor.left != nil {
			parent = successor
			successor = parent.left
		}
		// swap current and successor
		n.Val, successor.Val = successor.Val, n.Val
		n, successor = successor, n
		parent.maintainRelationship()
	}

	if n.isLeaf() {
		// black leaf node
		if n.isBlack() {
			t.deleteFixUp(n)
		}
		// delete
		if n.direction() == DirLeft {
			n.parent.left = nil
		} else {
			n.parent.right = nil
		}
	} else {
		// current node has a signle child
		// replace current with its child
		parent := n.parent
		var replacement *RBNode[T]
		if n.left != nil {
			replacement = n.left
		} else {
			replacement = n.right
		}
		switch n.direction() {
		case DirRoot:
			t.root = replacement
			break
		case DirLeft:
			parent.left = replacement
			break
		case DirRight:
			parent.right = replacement
			break
		}

		if !n.isRoot() {
			replacement.parent = parent
		}

		if n.isBlack() {
			if replacement.isRed() {
				replacement.color = Black
			} else {
				t.deleteFixUp(replacement)
			}
		}

		n = nil
	}

	t.cnt--
}

func (t *RBTree[T]) deleteFixUp(n *RBNode[T]) {
	if n.isRoot() {
		n.color = Black
		return
	}

	dir := n.direction()
	sibling := n.sibling()
	if sibling.isRed() {
		// case 1: current is black and sibling is red
		// step 1: recolor parent and sibling
		// step 2: rotate parent
		parent := n.parent
		parent.color = Red
		sibling.color = Black
		if dir == DirLeft {
			t.leftRotate(parent)
		} else {
			t.rightRotate(parent)
		}
		sibling = n.sibling()
	}

	var closeNephew, distantNephew *RBNode[T]
	var isCloseNephewBlack, isDistantNephewBlack bool
	if dir == DirLeft {
		closeNephew = sibling.left
		distantNephew = sibling.right
	} else {
		closeNephew = sibling.right
		distantNephew = sibling.left
	}
	if closeNephew == nil || closeNephew.isBlack() {
		isCloseNephewBlack = true
	}
	if distantNephew == nil || distantNephew.isBlack() {
		isDistantNephewBlack = true
	}

	if isCloseNephewBlack && isDistantNephewBlack {
		// case 2: sibling is black and has two black childs
		if n.parent.isRed() {
			n.parent.color = Black
			sibling.color = Red
		} else {
			sibling.color = Red
			t.deleteFixUp(n.parent)
		}
		return
	} else {
		if closeNephew != nil && closeNephew.isRed() {
			// case 3: sibling is black and close nephew is red
			closeNephew.color = Black
			sibling.color = Red
			if dir == DirLeft {
				t.rightRotate(sibling)
			} else {
				t.leftRotate(sibling)
			}
			sibling = n.sibling()
			if dir == DirLeft {
				closeNephew = sibling.left
				distantNephew = sibling.right
			} else {
				closeNephew = sibling.right
				distantNephew = sibling.left
			}
		}

		// case 4: sibling is black and distant nephew is red
		sibling.color = n.parent.color
		n.parent.color = Black
		if distantNephew != nil {
			distantNephew.color = Black
		}
		if dir == DirLeft {
			t.leftRotate(n.parent)
		} else {
			t.rightRotate(n.parent)
		}
		t.root.color = Black
		return
	}
}

func (t *RBTree[T]) InOrder() []T {
	res := make([]T, 0)
	t.inOrder(t.root, &res)
	return res
}

func (t *RBTree[T]) inOrder(n *RBNode[T], res *[]T) {
	if n == nil {
		return
	}

	if n.left != nil {
		t.inOrder(n.left, res)
	}
	*res = append(*res, n.Val)
	if n.right != nil {
		t.inOrder(n.right, res)
	}
}

Benchmark

goos: linux
goarch: amd64
pkg: github.com/elitedj/rbtree
cpu: AMD EPYC 7K62 48-Core Processor
BenchmarkInsert          4255707               324.2 ns/op
BenchmarkDelete         10957584               113.8 ns/op

参考

2-3-4 Tree –wiki

2-4 Tree Deletion

Red Black Tree –wiki

Red Black Tree –Paton, James

Red Black Tree Demo

Red Black Tree: Delete(删除资料)与Fixup(修正)

#Algorithm #Data Structure #Red Black Tree #Tree
下一页 BerryKV: 基于Bitcask模型的KV存储

相关

Treap
替罪羊树
可持久化并查集
可持久化数组
字典树(Trie)
可持久化线段树(主席树)