NOTE

2.8 红黑树

1. 红黑树是什么 - 一种平衡二叉查找树 - 满足二叉查找树的特征：任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值 - 满足5条特性即可保证平衡 - 节点要么是Red，要么是Black - 根节点是Black - 叶子节点（外部节点以及空节点）都是Black - Red

Data Structures & Algorithms创建于 2020/02/01更新于 2022/07/16historical

这是历史学习笔记，可能存在过时或不完整的理解。

1. 红黑树是什么

一种平衡二叉查找树
- 满足二叉查找树的特征：任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值
- 满足5条特性即可保证平衡
  - 节点要么是Red，要么是Black
  - 根节点是Black
  - 叶子节点（外部节点以及空节点）都是Black
  - Red节点的子节点都是Black
  - 从任一节点到叶子节点的所有路径都包含相同数目的Black

上面乍一看好像满足红黑树的5个特性，其实如图所示的那条路径只有2个黑节点，所以这个不是红黑树

1.1. 红黑树 vs 二叉平衡树

	红黑树	二叉平衡树
是否二叉搜索树	是	是
是否二叉平衡树	弱平衡(黑平衡)	强平衡
性质	五条特性	左右子树高度差不超过1
效率	插入删除快，查找慢	插入删除慢，查找快

2. 2-3树

满足二分搜索树的基本性质
不是一种二叉树，它有两种节点，一种可存放一个元素【左孩子<a<右孩子】，一种可存放两个元素【3个孩子，左孩子<b<中间孩子<c<右孩子】
插入2节点
插入3节点

2.1. 2-3树 vs 堆 vs 二分搜索树

2-3树绝对平衡
- 从根节点到任意叶子节点所经过的节点数量一定是相同的，对任意节点，左右子树的高度一定是相等的
堆完全二叉树，但是不是满二叉树
二分搜索树可能退化成链表

2.2. 2-3树和红黑树的等价性

3. 红黑树

3.1. 数据结构

同二叉搜索树

3.2. API

同二叉搜索树

3.3. 实现


const (
	//红色节点
	Red = true
	//黑色节点
	Black = false
)

type node struct {
	data  model.Comparable
	left  *node
	right *node
	color bool
}

func (n *node) String() string {
	s := "Black"
	if IsRed(n) {
		s = "Red"
	}
	return fmt.Sprintf("%v-%v", n.data, s)
}

func newNode(value model.Comparable) *node {
	return &node{
		data: value,
		//节点默认为 红色【添加时要先融合，故设为红色】
		color: Red,
	}
}

//判断节点的颜色
func IsRed(n *node) bool {
	//空节点为黑色
	if n == nil {
		return Black
	}
	return n.color
}

type RBTree struct {
	root   *node
	length int
}

func NewRBTree() *RBTree {
	return &RBTree{}
}

func (r *RBTree) String() string {
	s := fmt.Sprintf("length=%v, data={", r.Length())
	if r.root == nil {
		s += "}"
		return s
	}

	line := make([]*node, 0)
	allLines := make([][]*node, 0)

	queue := list.New()
	queue.PushBack(r.root)
	currentLineLast := r.root
	var nextLineLast *node
	for queue.Len() > 0 {
		n := queue.Remove(queue.Front()).(*node)
		line = append(line, n)
		if n.left != nil {
			queue.PushBack(n.left)
			nextLineLast = n.left
		}
		if n.right != nil {
			queue.PushBack(n.right)
			nextLineLast = n.right
		}
		if n == currentLineLast {
			currentLineLast = nextLineLast
			allLines = append(allLines, line)
			line = make([]*node, 0)
		}

	}

	for _, l := range allLines {
		s += fmt.Sprintf("%v\n", l)
	}
	s += "}"

	return s
}

func (r *RBTree) Length() int {
	return r.length
}

func (r *RBTree) IsEmpty() bool {
	return r.root == nil
}

//   node                     x
//  /   \     左旋转         /  \
// T1   x   --------->   node   T3
//     / \              /   \
//    T2 T3            T1   T2
func leftRotate(n *node) *node {
	x := n.right

	//左旋转
	n.right = x.left
	x.left = n

	x.color = n.color
	n.color = Red
	return x
}

//     node                   x
//    /   \     右旋转       /  \
//   x    T2   ------->   y   node
//  / \                       /  \
// y  T1                     T1  T2
func rightRotate(n *node) *node {
	x := n.left

	//右旋转
	n.left = x.right
	x.right = n

	x.color = n.color
	n.color = Red

	return x
}

func flipColors(n *node) {
	n.color = Red
	n.left.color = Black
	n.right.color = Black
}

func (r *RBTree) Add(data model.Comparable) {
	r.root = add(r.root, data)
	r.root.color = Black
	r.length++
}

func add(n *node, data model.Comparable) *node {
	if n == nil {
		return newNode(data)
	}
	if data.CompareTo(n.data) <= 0 {
		n.left = add(n.left, data)
	} else {
		n.right = add(n.right, data)
	}

	if IsRed(n.right) && !IsRed(n.left) {
		n = leftRotate(n)
	}
	if IsRed(n.left) && !IsRed(n.left.left) {
		n = rightRotate(n)
	}
	if IsRed(n.left) && IsRed(n.right) {
		flipColors(n)
	}
	return n
}

func (r *RBTree) Contains(data model.Comparable) bool {
	return contains(r.root, data)
}

func contains(node *node, data model.Comparable) bool {
	if node == nil {
		return false
	}

	if data.CompareTo(node.data) < 0 {
		return contains(node.left, data)
	} else if data.CompareTo(node.data) > 0 {
		return contains(node.right, data)
	} else {
		return true
	}
}

func (r *RBTree) PreOrder() []*node {
	datas := make([]*node, 0)
	preOrder(r.root, &datas)
	return datas
}

func preOrder(node *node, datas *[]*node) {
	if node == nil {
		return
	}
	*datas = append(*datas, node)
	preOrder(node.left, datas)
	preOrder(node.right, datas)
}

func (r *RBTree) InOrder() []*node {
	datas := make([]*node, 0)
	inOrder(r.root, &datas)
	return datas
}

func inOrder(node *node, datas *[]*node) {
	if node == nil {
		return
	}
	inOrder(node.left, datas)
	*datas = append(*datas, node)
	inOrder(node.right, datas)
}

func (r *RBTree) PostOrder() []*node {
	datas := make([]*node, 0)
	postOrder(r.root, &datas)
	return datas
}

func postOrder(node *node, datas *[]*node) {
	if node == nil {
		return
	}
	postOrder(node.left, datas)
	postOrder(node.right, datas)
	*datas = append(*datas, node)
}

func (r *RBTree) LevelOrder() []*node {
	datas := make([]*node, 0)
	levelOrder(r.root, &datas)
	return datas
}

func levelOrder(n *node, datas *[]*node) {
	if n == nil {
		return
	}
	queue := list.New()
	queue.PushBack(n)
	for queue.Len() > 0 {
		e := queue.Remove(queue.Front()).(*node)
		*datas = append(*datas, e)
		if e.left != nil {
			queue.PushBack(e.left)
		}
		if e.right != nil {
			queue.PushBack(e.right)
		}
	}
}

func (r *RBTree) Remove(data model.Comparable) {
	if r.root == nil {
		return
	}
	r.root = r.remove(r.root, data)
}

func (r *RBTree) remove(n *node, data model.Comparable) *node {
	//找到要删除的节点
	if data.CompareTo(n.data) < 0 {
		n.left = r.remove(n.left, data)
		return n
	} else if data.CompareTo(n.data) > 0 {
		n.right = r.remove(n.right, data)
		return n
	} else {
		//执行删除
		r.length--
		return doRemove(n)
	}
}

func doRemove(n *node) *node {
	//左子树为空
	//那么删除当前节点，把右子树上移为根节点
	//跟removeMin差不多
	if n.left == nil {
		rightNode := n.right
		n.right = nil
		return rightNode
	}
	//右子树为空
	//那么删除当前节点，把左子树上移为根节点
	//跟removeMax差不多
	if n.right == nil {
		leftNode := n.left
		n.left = nil
		return leftNode
	}

	//左右子树都不为空
	//先找到当前节点的前继，即右子树的最小节点代替本节点
	successor := min(n.right)
	successor.right = removeMin(n.right)
	successor.left = n.left
	//删除当前节点
	n.left = nil
	n.right = nil
	return successor
}

func (r *RBTree) Max() *node {
	if r.root == nil {
		return nil
	}
	return max(r.root)
}

func max(n *node) *node {
	if n.right == nil {
		return n
	}
	return max(n.right)
}

func (r *RBTree) Min() *node {
	if r.root == nil {
		return nil
	}
	return min(r.root)
}

func min(n *node) *node {
	if n.left == nil {
		return n
	}
	return min(n.left)
}

func (r *RBTree) RemoveMax() *node {
	e := r.Max()
	r.root = removeMax(r.root)
	r.length--
	return e
}

func removeMax(n *node) *node {
	if n == nil {
		return nil
	}
	//右子树为空，说明当前节点就是最大节点
	//那么删除当前节点，把左子树上移为根节点
	if n.right == nil {
		leftNode := n.left
		n.left = nil
		return leftNode
	}
	n.right = removeMax(n.right)
	return n
}

func (r *RBTree) RemoveMin() *node {
	e := r.Min()
	r.root = removeMin(r.root)
	r.length--
	return e
}

func removeMin(n *node) *node {
	if n == nil {
		return nil
	}
	//左子树为空，说明当前节点就是最小节点
	//那么删除当前节点，把右子树上移为根节点
	if n.left == nil {
		rightNode := n.right
		n.right = nil
		return rightNode
	}
	n.left = removeMin(n.left)
	return n
}

3.3.1. 测试


func TestRBTree(t *testing.T) {
	rbTree := NewRBTree()

	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	e4 := model.NewElement(4)
	e5 := model.NewElement(5)

	rbTree.Add(e3)
	rbTree.Add(e2)
	rbTree.Add(e4)
	rbTree.Add(e1)
	rbTree.Add(e5)

	fmt.Println("初始数据：", rbTree)
	fmt.Println("层序遍历：", rbTree.LevelOrder())
	fmt.Println("前序遍历：", rbTree.PreOrder())
	fmt.Println("中序遍历：", rbTree.InOrder())
	fmt.Println("后序遍历：", rbTree.PostOrder())

	fmt.Println("最小节点：", rbTree.Min())
	fmt.Println("最大节点：", rbTree.Max())
	fmt.Println("删除最小节点：", rbTree.RemoveMin())
	fmt.Println("删除最小节点后：", rbTree)
	rbTree.Remove(e3)
	fmt.Println("删除根节点后：", rbTree)

}