分类目录归档:算法和数据结构

Algorithm和Structrues

Algorithm和Structrues

1. 哪些排序算法是稳定的

选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法.

排序算法的稳定性这个应该是清晰明了的,通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj,Ai原来在位置前,排序后Ai还是要在Aj位置前。

其次,说一下稳定性的好处。排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。

基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。另外,如果排序算法稳定,对基于比较的排序算法而言,元素交换的次数可能会少一些。

现在我们来分析一下常见的排序算法的稳定性。

(1)冒泡排序

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。
所以,如果两个元素相等,我想你是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

(2)选择排序

选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n – 1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。
比较拗口,举个例子,序列5 8 5 2 9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。

(3)插入排序

插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。
如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

(4)快速排序

快速排序有两个方向,左边的i下标一直往右走,当a[i] <= a[center index],其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的j下标一直往左走,当a[j] > a[center_index]。如果i和j都走不动了,i <= j,交换a[i]a[j],重复上面的过程,直到i > j。 交换a[j]a[center_index],完成一趟快速排序。
在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为5 3 3 4 3 8 9 10 11,现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j]交换的时刻。

(5)归并排序

归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定性。那么,在短的有序序列合并的过程中,稳定是是否受到破坏?没有,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结果序列的前面,这样就保证了稳定性。所以,归并排序也是稳定的排序算法。

(6)基数排序

基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以其是稳定的排序算法。

(7)希尔排序(shell)

希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小, 插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比O(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。

(8)堆排序

我们知道堆的结构是节点i的孩子为2 * i2 * i + 1节点,大顶堆要求父节点大于等于其2个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列,堆排序的过程是从第n / 2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n / 2 - 1n / 2 - 2, … 1这些个父节点选择元素时,就会破坏稳定性。有可能第n / 2个父节点交换把后面一个元素交换过去了,而第n / 2 - 1个父节点把后面一个相同的元素没 有交换,那么这2个相同的元素之间的稳定性就被破坏了。

所以,堆排序不是稳定的排序算法。

因此会有: 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法

2. 给定一个二叉树,判断其是否是一个有效的二叉搜索树

什么是二叉树(Binary Tree)?

每个结点至多拥有两棵子树的树结构(即二叉树中不存在度大于2的结点)。并且,二叉树的子树有左右之分,其次序不能任意颠倒。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。

上面概念中提到了“度”的概念,“度”其实就是某个节点子节点的数量。如果某个节点的子节点数量为1,则该节点的度为1,如果有8个子节点,则度为8,以此类推。

假设一个二叉搜索树具有如下特征:

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
   2
  / \
 1   3
输出: true
示例 2:
输入:
     5
    / \
   1   4
  / \
 3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ,但是其右子节点值为 4 。

可以直接按照定义比较大小,比 root 节点小的都在左边,比 root 节点大的都在右边:

type TreeNode struct {
      Val int
      Left *TreeNode
      Right *TreeNode
}

func isValidBST(root *TreeNode) bool {
    return isValid(root, math.MinInt64, math.MaxInt64)
}

func isValid(root *TreeNode, min, max int) bool {
    if root == nil {
        return true
    }
    if root.Val <= min {
        return false
    }
    if root.Val >= max {
        return false
    }
    return isValid(root.Left, min, root.Val) && isValid(root.Right, root.Val, max)
}

3. 排序算法

排序算法又分为稳定性算法和不稳定性算法:

  • 稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序。

  • 不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序。

  • 冒泡排序

func main() {
    var arr = []int{9,10,11,5,3,4,27,2,1,3,20}
    //升序
    bubbleAscendingSort(arr)
    //降序
    bubbleDescendingSort(arr)
}

//升序
func bubbleAscendingSort(arr []int) {
    for i :=0; i < len(arr)-1; i++ {
        for j := i+1; j< len(arr); j++ {
            if (arr[i] > arr[j]) {
                arr[i],arr[j] = arr[j],arr[i]
            }
        }
    }

    fmt.Println("bubbleAscendingSort:",arr)
}

//降序
func bubbleDescendingSort(arr []int) {
    for i :=0; i < len(arr)-1; i++ {
        for j := i+1; j< len(arr); j++ {
            if (arr[i] < arr[j]) {
                arr[i],arr[j] = arr[j],arr[i]
            }
        }
    }

    fmt.Println("bubbleDescendingSort:",arr)
}

运行结果:

bubbleAscendingSort: [1 2 3 3 4 5 9 10 11 20 27]

bubbleDescendingSort: [27 20 11 10 9 5 4 3 3 2 1]
  • 选择排序
func main() {
    var arr = []int{19,28,17,5,13,4,6,7,9,3,10}
    //升序
    selectAscendingSort(arr)
    //降序
    selectDescendingSort(arr)
}

//升序
func selectAscendingSort(arr []int) {
    l := len(arr)
    m := len(arr) - 1
    for i := 0; i < m; i++ {
        k := i
        for j := i+1; j < l; j++ {
            if arr[k] > arr[j] {
                k = j
            }
        }
        if k != i {
            arr[k],arr[i] = arr[i],arr[k]
        }
    }

    fmt.Println("selectAscendingSort:",arr)
}

//降序
func selectDescendingSort(arr []int) {
    l := len(arr)
    m := len(arr) - 1
    for i := 0; i < m; i++ {
        k := i
        for j := i+1; j < l; j++ {
            if arr[k] < arr[j] {
                k = j
            }
        }
        if k != i {
            arr[k],arr[i] = arr[i],arr[k]
        }
    }

    fmt.Println("selectDescendingSort:",arr)
}

运行结果:

selectDescendingSort: [3 4 5 6 7 9 10 13 17 19 28]

selectAscendingSort: [28 19 17 13 10 9 7 6 5 4 3]
  • 插入排序
func main() {
    var arr = []int{19,13,27,15,3,4,26,12,1,0}
    insertSort(arr)
    fmt.Println("insertSort:",arr)
}

func insertSort(arr []int) {
    n := len(arr)
    if n < 2 {
        return
    }
    for i := 1; i < n; i++ {
        for j := i; j >0 && arr[j] < arr[j-1]; j-- {
            arr[j], arr[j-1] = arr[j-1], arr[j]
        }
    }
}

运行结果:

insertSort: [0 1 3 4 12 13 15 19 26 27]
  • 希尔排序
func main() {
    var arr = []int{19,8,27,15,3,17,6,2,1,0}
    shellSort(arr)
    fmt.Println("shellSort:",arr)
}
func shellSort(arr []int) {
    n := len(arr)
    h := 1

    //寻找合适的间隔h
    for h < n/3 {
        h = 3*h +1
    }

    for h >= 1 {
        for i := h; i < n; i++ {
            for j := i; j >= h && arr[j] < arr[j-1]; j -= h {
                arr[j], arr[j-1] = arr[j-1], arr[j]
            }
        }
        h /= 3
    }
}

运行结果:

shellSort: [0 1 2 3 6 8 15 17 19 27]
  • 归并排序
func main() {
    array := []int{55, 94, 87, 12, 4, 32, 11,8, 39, 42, 64, 53, 70, 12, 9}
    fmt.Println("before MergeSort",array)
    array = MergeSort(array)
    fmt.Println("after MergeSort:",array)
}

func MergeSort(array []int) []int{
    n := len(array)
    if n < 2 {
        return array
    }
    key := n / 2
    left := MergeSort(array[0:key])
    right := MergeSort(array[key:])
    return merge(left, right)
}

func merge(left []int, right []int) []int{
    tmp := make([]int, 0)
    i, j := 0,0
    for  i < len(left) && j < len(right) {
        if left[i] < right[j]{
            tmp = append(tmp, left[i])
            i ++
        }else{
            tmp = append(tmp, right[j])
            j ++
        }
    }
    tmp = append(tmp, left[i:]...)
    tmp = append(tmp, right[j:]...)
    return tmp
}

运行结果:

before MergeSort [55 94 87 12 4 32 11 8 39 42 64 53 70 12 9]
after MergeSort: [4 8 9 11 12 12 32 39 42 53 55 64 70 87 94]
  • 快速排序
func main() {
    var arr = []int{19,8,16,15,23,34,6,3,1,0,2,9,7}
    quickAscendingSort(arr, 0, len(arr)-1)
    fmt.Println("quickAscendingSort:",arr)

    quickDescendingSort(arr, 0, len(arr)-1)
    fmt.Println("quickDescendingSort:",arr)
}

//升序
func quickAscendingSort(arr []int, start, end int) {
    if (start < end) {
        i, j := start, end
        key := arr[(start + end)/2]
        for i <= j {
            for arr[i] < key {
                i++
            }
            for arr[j] > key {
                j--
            }
            if i <= j {
                arr[i], arr[j] = arr[j], arr[i]
                i++
                j--
            }
        }

        if start < j {
            quickAscendingSort(arr, start, j)
        }
        if end > i {
            quickAscendingSort(arr, i, end)
        }
    }
}

//降序
func quickDescendingSort(arr []int, start, end int) {
    if (start < end) {
        i, j := start, end
        key := arr[(start + end)/2]
        for i <= j {
            for arr[i] > key {
                i++
            }
            for arr[j] < key {
                j--
            }
            if i <= j {
                arr[i], arr[j] = arr[j], arr[i]
                i++
                j--
            }
        }

        if start < j {
            quickDescendingSort(arr, start, j)
        }
        if end > i {
            quickDescendingSort(arr, i, end)
        }
    }
}

运行结果:

quickAscendingSort: [0 1 2 3 6 7 8 9 15 16 19 23 34]
quickDescendingSort: [34 23 19 16 15 9 8 7 6 3 2 1 0]
  • 堆排序
func main()  {
    array := []int{52,16,37,2,3,32,12,27,19,42,29,13,37,12,9}
    HeapSort(array)
    fmt.Println("HeapSort:",array)
}

func HeapSort(array []int) {
    m := len(array)
    s := m/2
    for i := s; i > -1; i-- {
        heap(array, i, m-1)
    }
    for i := m-1; i > 0; i-- {
        array[i], array[0] = array[0], array[i]
        heap(array, 0, i-1)
    }
}

func heap(array []int, i, end int){
    l := 2*i+1
    if l > end {
        return
    }
    n := l
    r := 2*i+2
    if r <= end && array[r]>array[l]{
        n = r
    }
    if array[i] > array[n]{
        return
    }
    array[n], array[i] = array[i], array[n]
    heap(array, n, end)
}

运行结果:

HeapSort: [2 3 9 12 12 13 16 19 27 29 32 37 37 42 52]
  • 桶排序
func main()  {
    array := []int{31,16,37,2,13,32,10,27,7,42,29,18,28,12,9,}
    BucketSort(array)
    fmt.Println("BucketSort:",array)
}

func sortInBucket(bucket []int) {//此处实现插入排序方式,其实可以用任意其他排序方式
    length := len(bucket)
    if length == 1 {return}

    for i := 1; i < length; i++ {
        backup := bucket[i]
        j := i -1;
        //将选出的被排数比较后插入左边有序区
        for  j >= 0 && backup < bucket[j] {//注意j >= 0必须在前边,否则会数组越界
            bucket[j+1] = bucket[j]//移动有序数组
            j -- //反向移动下标
        }
        bucket[j + 1] = backup //插队插入移动后的空位
    }
}
//获取数组最大值
func getMaxInArr(arr []int) int{
    max := arr[0]
    for i := 1; i < len(arr); i++ {
        if arr[i] > max{ max = arr[i]}
    }
    return max
}

//桶排序
func BucketSort(arr []int) []int {
    //桶数
    num := len(arr)
    //k(数组最大值)
    max := getMaxInArr(arr)
    //二维切片
    buckets := make([][]int, num)

    //分配入桶
    index := 0
    for i := 0; i < num; i++ {
        index = arr[i] * (num-1) /max//分配桶index = value * (n-1) /k

        buckets[index] = append(buckets[index], arr[i])
    }
    //桶内排序
    tmpPos := 0
    for i := 0; i < num; i++ {
        bucketLen := len(buckets[i])
        if bucketLen > 0{
            sortInBucket(buckets[i])

            copy(arr[tmpPos:], buckets[i])

            tmpPos += bucketLen
        }
    }

    return arr

运行结果:

BucketSort: [2 7 9 10 12 13 16 18 27 28 29 31 32 37 42]
  • 计数排序
func main()  {
    array := []int{69,16,48,2,3,32,10,27,17,42,29,8,28,12,9,}
    countingSort(array,array[0])
    fmt.Println("BucketSort:",array)
}

func countingSort(arr []int, maxValue int) []int {
    bucketLen := maxValue + 1
    bucket := make([]int, bucketLen) // 初始为0的数组

    sortedIndex := 0
    length := len(arr)

    for i := 0; i < length; i++ {
        bucket[arr[i]] += 1
    }

    for j := 0; j < bucketLen; j++ {
        for bucket[j] > 0 {
            arr[sortedIndex] = j
            sortedIndex += 1
            bucket[j] -= 1
        }
    }

    return arr
}

运行结果:

countingSort: [2 3 8 9 10 12 16 17 27 28 29 32 42 48 69]
  • 基数排序
func main() {
    array := []int{12, 3, 8, 5, 9, 11, 23, 36,20,28,21}
    fmt.Println("before radixSort:",array)

    radixSort(array)
    fmt.Println("after radixSort:",array)
}

//获取数组的最大值
func maxValue(arr []int) (ret int) {
    ret = 1 
    var key int = 10
    for i := 0; i < len(arr); i++ {
        for arr[i] >= key {
            key = key * 10
            ret++
        }
    }
    return
}

func radixSort(arr []int) {
    key := maxValue(arr)
    tmp := make([]int, len(arr), len(arr))
    count := new([10]int)
    radix := 1
    var i, j, k int
    for i = 0; i < key; i++ { //进行key次排序
        for j = 0; j < 10; j++ {
            count[j] = 0
        }
        for j = 0; j < len(arr); j++ {
            k = (arr[j] / radix) % 10
            count[k]++
        }

        for j = 1; j < 10; j++ { //将tmp中的为准依次分配给每个桶
            count[j] = count[j-1] + count[j]
        }
        for j = len(arr) - 1; j >= 0; j-- {
            k = (arr[j] / radix) % 10
            tmp[count[k]-1] = arr[j]
            count[k]--
        }
        for j = 0; j <len(arr); j++ {
            arr[j] = tmp[j]
        }
        radix = radix * 10
    }
}

运行结果:

before radixSort: [12 3 8 5 9 11 23 36 20 28 21]

after radixSort: [3 5 8 9 11 12 20 21 23 28 36]

4. 如何通过递归反转单链表

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。

每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。

由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。

链表最明显的好处就是,常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序,数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点,但是不允许随机存取。

链表有很多种不同的类型:单向链表,双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。

package main

import "fmt"

// 通过递归反转单链表
type Node struct {
    Value int
    NextNode *Node
}


func Param(node *Node){
    for node !=nil{
        fmt.Print(node.Value,"--->")
        node = node.NextNode
    }
    fmt.Println()
}

func reverse(headNode *Node) *Node{
    if headNode ==nil {
        return headNode
    }
    if headNode.NextNode == nil{
        return headNode
    }
    var newNode = reverse(headNode.NextNode)
    headNode.NextNode.NextNode = headNode
    headNode.NextNode = nil
    return newNode
}
func main() {
    var node1 = &Node{}
    node1.Value = 1
    node2 := new(Node)
    node2.Value = 2
    node3 := new(Node)
    node3.Value = 3
    node4 := new(Node)
    node4.Value = 4
    node1.NextNode = node2
    node2.NextNode = node3
    node3.NextNode = node4
    Param(node1)
    reverseNode := reverse(node1)
    Param(reverseNode)
}

运行结果:

1--->2--->3--->4--->
4--->3--->2--->1--->

5. 链表和数组相比有什么优缺点

数组是一块连续的空间,声明时长度就要确定,链表是一块不连续的动态空间,长度可变,数组的优点是速度快,数据操作直接使用偏移地址, 链表需要按顺序检索节点,效率低,链表的优点是可以快速插入和删除节点,大小动态分配长度不需要固定.

链表不存在越界问题,数组有越界问题.

6. 通常一般会用到哪些数据结构

数据结构是计算机存储、组织数据的方式。对于特定的数据结构(比如数组),有些操作效率很高(读某个数组元素),有些操作的效率很低(删除某个数组元素)。开发者的目标是为当前的问题选择最优的数据结构。

  1. 数组:是最常用的数据结构了。其他数据结构,比如栈和队列都是由数组衍生出来的。
  2. 栈:是限定仅表尾进行插入和删除操作的线性表 。
  3. 队列
  4. 链表
  5. 前缀树
  6. 哈希表

算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法,厄米变形模型,随机森林算法。

数据对象的运算和操作:计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合,成为该计算机系统的指令系统。

一个计算机的基本运算和操作有如下四类:

  • 算术运算:加减乘除等运算.
  • 逻辑运算:或、且、非等运算.
  • 关系运算:大于、小于、等于、不等于等运算.
  • 数据传输:输入、输出、赋值等运算.

R-B Tree

30张图带你彻底理解红黑树

写在前面

当在10亿数据进行不到30次比较就能查找到目标时,不禁感叹编程之魅力!人类之伟大呀! —— 学红黑树有感。

终于,在学习了几天的红黑树相关的知识后,我想把我所学所想和所感分享给大家。红黑树是一种比较难的数据结构,要完全搞懂非常耗时耗力,红黑树怎么自平衡?什么时候需要左旋或右旋?插入和删除破坏了树的平衡后怎么处理?等等一连串的问题在学习前困扰着我。如果你在学习过程中也会存在我的疑问,那么本文对你会有帮助,本文帮助你全面、彻底地理解红黑树!

本文将通过图文的方式讲解红黑树的知识点,并且不会涉及到任何代码,相信我,在懂得红黑树实现原理前,看代码会一头雾水的,当原理懂了,代码也就按部就班写而已,没任何难度。

阅读本文你需具备知识点:

  • 二叉查找树
  • 完美平衡二叉树

事不宜迟,让我们进入正题吧。


正文

红黑树也是二叉查找树,我们知道,二叉查找树这一数据结构并不难,而红黑树之所以难是难在它是自平衡的二叉查找树,在进行插入和删除等可能会破坏树的平衡的操作时,需要重新自处理达到平衡状态。现在在脑海想下怎么实现?是不是太多情景需要考虑了?啧啧,先别急,通过本文的学习后,你会觉得,其实也不过如此而已。好吧,我们先来看下红黑树的定义和一些基本性质。

红黑树定义和性质

红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质:

  • 性质1:每个节点要么是黑色,要么是红色。
  • 性质2:根节点是黑色。
  • 性质3:每个叶子节点(NIL)是黑色。
  • 性质4:每个红色结点的两个子结点一定都是黑色。
  • 性质5:任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

从性质5又可以推出:

  • 性质5.1:如果一个结点存在黑子结点,那么该结点肯定有两个子结点

图1就是一颗简单的红黑树。其中Nil为叶子结点(2020/01/16补充:图1中的红色结点H和M同样存在叶子子结点,后文的图类似,不再阐明。感谢评论区的同学提醒,带来误解抱歉。),并且它是黑色的。(值得提醒注意的是,在Java中,叶子结点是为null的结点。)

图1 一颗简单的红黑树

红黑树并不是一个完美平衡二叉查找树,从图1可以看到,根结点P的左子树显然比右子树高,但左子树和右子树的黑结点的层数是相等的,也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点(性质5)。所以我们叫红黑树这种平衡为黑色完美平衡

介绍到此,为了后面讲解不至于混淆,我们还需要来约定下红黑树一些结点的叫法,如图2所示。

img

图2 结点叫法约定

我们把正在处理(遍历)的结点叫做当前结点,如图2中的D,它的父亲叫做父结点,它的父亲的另外一个子结点叫做兄弟结点,父亲的父亲叫做祖父结点。

前面讲到红黑树能自平衡,它靠的是什么?三种操作:左旋、右旋和变色。

  • 左旋:以某个结点作为支点(旋转结点),其右子结点变为旋转结点的父结点,右子结点的左子结点变为旋转结点的右子结点,左子结点保持不变。如图3。
  • 右旋:以某个结点作为支点(旋转结点),其左子结点变为旋转结点的父结点,左子结点的右子结点变为旋转结点的左子结点,右子结点保持不变。如图4。
  • 变色:结点的颜色由红变黑或由黑变红。

图3 左旋

图4 右旋

上面所说的旋转结点也即旋转的支点,图4和图5中的P结点。
我们先忽略颜色,可以看到旋转操作不会影响旋转结点的父结点,父结点以上的结构还是保持不变的。
左旋只影响旋转结点和其右子树的结构,把右子树的结点往左子树挪了。
右旋只影响旋转结点和其左子树的结构,把左子树的结点往右子树挪了。

所以旋转操作是局部的。另外可以看出旋转能保持红黑树平衡的一些端详了:当一边子树的结点少了,那么向另外一边子树“借”一些结点;当一边子树的结点多了,那么向另外一边子树“租”一些结点。

但要保持红黑树的性质,结点不能乱挪,还得靠变色了。怎么变?具体情景又不同变法,后面会具体讲到,现在只需要记住红黑树总是通过旋转和变色达到自平衡

balabala了这么多,相信你对红黑树有一定印象了,那么现在来考考你:

*思考题1:黑结点可以同时包含一个红子结点和一个黑子结点吗?* (答案见文末)

接下来先讲解红黑树的查找热热身。


红黑树查找

因为红黑树是一颗二叉平衡树,并且查找不会破坏树的平衡,所以查找跟二叉平衡树的查找无异:

  1. 从根结点开始查找,把根结点设置为当前结点;
  2. 若当前结点为空,返回null;
  3. 若当前结点不为空,用当前结点的key跟查找key作比较;
  4. 若当前结点key等于查找key,那么该key就是查找目标,返回当前结点;
  5. 若当前结点key大于查找key,把当前结点的左子结点设置为当前结点,重复步骤2;
  6. 若当前结点key小于查找key,把当前结点的右子结点设置为当前结点,重复步骤2;

如图5所示。

图5 二叉树查找流程图

非常简单,但简单不代表它效率不好。正由于红黑树总保持黑色完美平衡,所以它的查找最坏时间复杂度为O(2lgN),也即整颗树刚好红黑相隔的时候。能有这么好的查找效率得益于红黑树自平衡的特性,而这背后的付出,红黑树的插入操作功不可没~


红黑树插入

插入操作包括两部分工作:一查找插入的位置;二插入后自平衡。查找插入的父结点很简单,跟查找操作区别不大:

  1. 从根结点开始查找;
  2. 若根结点为空,那么插入结点作为根结点,结束。
  3. 若根结点不为空,那么把根结点作为当前结点;
  4. 若当前结点为null,返回当前结点的父结点,结束。
  5. 若当前结点key等于查找key,那么该key所在结点就是插入结点,更新结点的值,结束。
  6. 若当前结点key大于查找key,把当前结点的左子结点设置为当前结点,重复步骤4;
  7. 若当前结点key小于查找key,把当前结点的右子结点设置为当前结点,重复步骤4;

如图6所示。

图6 红黑树插入位置查找

ok,插入位置已经找到,把插入结点放到正确的位置就可以啦,但插入结点是应该是什么颜色呢?答案是红色。理由很简单,红色在父结点(如果存在)为黑色结点时,红黑树的黑色平衡没被破坏,不需要做自平衡操作。但如果插入结点是黑色,那么插入位置所在的子树黑色结点总是多1,必须做自平衡。

所有插入情景如图7所示。

图7 红黑树插入情景

嗯,插入情景很多呢,8种插入情景!但情景1、2和3的处理很简单,而情景4.2和情景4.3只是方向反转而已,懂得了一种情景就能推出另外一种情景,所以总体来看,并不复杂,后续我们将一个一个情景来看,把它彻底搞懂。

另外,根据二叉树的性质,除了情景2,所有插入操作都是在叶子结点进行的。这点应该不难理解,因为查找插入位置时,我们就是在找子结点为空的父结点的。

在开始每个情景的讲解前,我们还是先来约定下,如图8所示。

图8 插入操作结点的叫法约定

图8的字母并不代表结点Key的大小。I表示插入结点,P表示插入结点的父结点,S表示插入结点的叔叔结点,PP表示插入结点的祖父结点。

好了,下面让我们一个一个来分析每个插入的情景以其处理。

插入情景1:红黑树为空树

最简单的一种情景,直接把插入结点作为根结点就行,但注意,根据红黑树性质2:根节点是黑色。还需要把插入结点设为黑色。

处理:把插入结点作为根结点,并把结点设置为黑色

插入情景2:插入结点的Key已存在

插入结点的Key已存在,既然红黑树总保持平衡,在插入前红黑树已经是平衡的,那么把插入结点设置为将要替代结点的颜色,再把结点的值更新就完成插入。

处理:

  • 把I设为当前结点的颜色
  • 更新当前结点的值为插入结点的值
插入情景3:插入结点的父结点为黑结点

由于插入的结点是红色的,并不会影响红黑树的平衡,直接插入即可,无需做自平衡。

处理:直接插入

插入情景4:插入结点的父结点为红结点

再次回想下红黑树的性质2:根结点是黑色。如果插入的父结点为红结点,那么该父结点不可能为根结点,所以插入结点总是存在祖父结点。这点很重要,因为后续的旋转操作肯定需要祖父结点的参与。

情景4又分为很多子情景,下面将进入重点部分,各位看官请留神了。

插入情景4.1:叔叔结点存在并且为红结点
从红黑树性质4可以,祖父结点肯定为黑结点,因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是:黑红红。显然最简单的处理方式是把其改为:红黑红。如图9和图10所示。

处理:

  • 将P和S设置为黑色
  • 将PP设置为红色
  • 把PP设置为当前插入结点

图9 插入情景4.1_1

图10 插入情景4.1_2

可以看到,我们把PP结点设为红色了,如果PP的父结点是黑色,那么无需再做任何处理;但如果PP的父结点是红色,根据性质4,此时红黑树已不平衡了,所以还需要把PP当作新的插入结点,继续做插入操作自平衡处理,直到平衡为止。

试想下PP刚好为根结点时,那么根据性质2,我们必须把PP重新设为黑色,那么树的红黑结构变为:黑黑红。换句话说,从根结点到叶子结点的路径中,黑色结点增加了。这也是唯一一种会增加红黑树黑色结点层数的插入情景

我们还可以总结出另外一个经验:红黑树的生长是自底向上的。这点不同于普通的二叉查找树,普通的二叉查找树的生长是自顶向下的。

插入情景4.2:叔叔结点不存在或为黑结点,并且插入结点的父亲结点是祖父结点的左子结点
单纯从插入前来看,也即不算情景4.1自底向上处理时的情况,叔叔结点非红即为叶子结点(Nil)。因为如果叔叔结点为黑结点,而父结点为红结点,那么叔叔结点所在的子树的黑色结点就比父结点所在子树的多了,这不满足红黑树的性质5。后续情景同样如此,不再多做说明了。

前文说了,需要旋转操作时,肯定一边子树的结点多了或少了,需要租或借给另一边。插入显然是多的情况,那么把多的结点租给另一边子树就可以了。

插入情景4.2.1:插入结点是其父结点的左子结点
处理:

  • 将P设为黑色
  • 将PP设为红色
  • 对PP进行右旋

图11 插入情景4.2.1

由图11可得,左边两个红结点,右边不存在,那么一边一个刚刚好,并且因为为红色,肯定不会破坏树的平衡。

咦,可以把P设为红色,I和PP设为黑色吗?答案是可以!看过《算法:第4版》的同学可能知道,书中讲解的就是把P设为红色,I和PP设为黑色。但把P设为红色,显然又会出现情景4.1的情况,需要自底向上处理,做多了无谓的操作,既然能自己消化就不要麻烦祖辈们啦~

插入情景4.2.2:插入结点是其父结点的右子结点
这种情景显然可以转换为情景4.2.1,如图12所示,不做过多说明了。

处理:

  • 对P进行左旋
  • 把P设置为插入结点,得到情景4.2.1
  • 进行情景4.2.1的处理

图12 插入情景4.2.2

插入情景4.3:叔叔结点不存在或为黑结点,并且插入结点的父亲结点是祖父结点的右子结点
该情景对应情景4.2,只是方向反转,不做过多说明了,直接看图。

插入情景4.3.1:插入结点是其父结点的右子结点
处理:

  • 将P设为黑色
  • 将PP设为红色
  • 对PP进行左旋

图13 插入情景4.3.1

插入情景4.3.2:插入结点是其父结点的左子结点
处理:

  • 对P进行右旋
  • 把P设置为插入结点,得到情景4.3.1
  • 进行情景4.3.1的处理

图14 插入情景4.3.2

好了,讲完插入的所有情景了。可能又同学会想:上面的情景举例的都是第一次插入而不包含自底向上处理的情况,那么上面所说的情景都适合自底向上的情况吗?答案是肯定的。理由很简单,但每棵子树都能自平衡,那么整棵树最终总是平衡的。好吧,在出个习题,请大家拿出笔和纸画下试试(请务必动手画下,加深印象):

*习题1:请画出图15的插入自平衡处理过程。*(答案见文末)

图15 习题1


红黑树删除

红黑树插入已经够复杂了,但删除更复杂,也是红黑树最复杂的操作了。但稳住,胜利的曙光就在前面了!

红黑树的删除操作也包括两部分工作:一查找目标结点;而删除后自平衡。查找目标结点显然可以复用查找操作,当不存在目标结点时,忽略本次操作;当存在目标结点时,删除后就得做自平衡处理了。删除了结点后我们还需要找结点来替代删除结点的位置,不然子树跟父辈结点断开了,除非删除结点刚好没子结点,那么就不需要替代。

二叉树删除结点找替代结点有3种情情景:

  • 情景1:若删除结点无子结点,直接删除
  • 情景2:若删除结点只有一个子结点,用子结点替换删除结点
  • 情景3:若删除结点有两个子结点,用后继结点(大于删除结点的最小结点)替换删除结点

补充说明下,情景3的后继结点是大于删除结点的最小结点,也是删除结点的右子树种最左结点。那么可以拿前继结点(删除结点的左子树最右结点)替代吗?可以的。但习惯上大多都是拿后继结点来替代,后文的讲解也是用后继结点来替代。另外告诉大家一种找前继和后继结点的直观的方法(不知为何没人提过,大家都知道?):把二叉树所有结点投射在X轴上,所有结点都是从左到右排好序的,所有目标结点的前后结点就是对应前继和后继结点。如图16所示。

图16 二叉树投射x轴后有序

接下来,讲一个重要的思路:删除结点被替代后,在不考虑结点的键值的情况下,对于树来说,可以认为删除的是替代结点!话很苍白,我们看图17。在不看键值对的情况下,图17的红黑树最终结果是删除了Q所在位置的结点!这种思路非常重要,大大简化了后文讲解红黑树删除的情景!

图17 删除结点换位思路

基于此,上面所说的3种二叉树的删除情景可以相互转换并且最终都是转换为情景1!

  • 情景2:删除结点用其唯一的子结点替换,子结点替换为删除结点后,可以认为删除的是子结点,若子结点又有两个子结点,那么相当于转换为情景3,一直自顶向下转换,总是能转换为情景1。(对于红黑树来说,根据性质5.1,只存在一个子结点的结点肯定在树末了)
  • 情景3:删除结点用后继结点(肯定不存在左结点),如果后继结点有右子结点,那么相当于转换为情景2,否则转为为情景1。

二叉树删除结点情景关系图如图18所示。

图18 二叉树删除情景转换

综上所述,删除操作删除的结点可以看作删除替代结点,而替代结点最后总是在树末。有了这结论,我们讨论的删除红黑树的情景就少了很多,因为我们只考虑删除树末结点的情景了。

同样的,我们也是先来总体看下删除操作的所有情景,如图19所示。

图19 红黑树删除情景

哈哈,是的,即使简化了还是有9种情景!但跟插入操作一样,存在左右对称的情景,只是方向变了,没有本质区别。同样的,我们还是来约定下,如图20所示。

图20 删除操作结点的叫法约定

图20的字母并不代表结点Key的大小。R表示替代结点,P表示替代结点的父结点,S表示替代结点的兄弟结点,SL表示兄弟结点的左子结点,SR表示兄弟结点的右子结点。灰色结点表示它可以是红色也可以是黑色。

值得特别提醒的是,R是即将被替换到删除结点的位置的替代结点,在删除前,它还在原来所在位置参与树的子平衡,平衡后再替换到删除结点的位置,才算删除完成。

万事具备,我们进入最后的也是最难的讲解。

删除情景1:替换结点是红色结点

我们把替换结点换到了删除结点的位置时,由于替换结点时红色,删除也了不会影响红黑树的平衡,只要把替换结点的颜色设为删除的结点的颜色即可重新平衡。

处理:颜色变为删除结点的颜色

删除情景2:替换结点是黑结点

当替换结点是黑色时,我们就不得不进行自平衡处理了。我们必须还得考虑替换结点是其父结点的左子结点还是右子结点,来做不同的旋转操作,使树重新平衡。

删除情景2.1:替换结点是其父结点的左子结点
删除情景2.1.1:替换结点的兄弟结点是红结点
若兄弟结点是红结点,那么根据性质4,兄弟结点的父结点和子结点肯定为黑色,不会有其他子情景,我们按图21处理,得到删除情景2.1.2.3(后续讲解,这里先记住,此时R仍然是替代结点,它的新的兄弟结点SL和兄弟结点的子结点都是黑色)。

处理:

  • 将S设为黑色
  • 将P设为红色
  • 对P进行左旋,得到情景2.1.2.3
  • 进行情景2.1.2.3的处理

图21 删除情景2.1.1

删除情景2.1.2:替换结点的兄弟结点是黑结点
当兄弟结点为黑时,其父结点和子结点的具体颜色也无法确定(如果也不考虑自底向上的情况,子结点非红即为叶子结点Nil,Nil结点为黑结点),此时又得考虑多种子情景。

删除情景2.1.2.1:替换结点的兄弟结点的右子结点是红结点,左子结点任意颜色
即将删除的左子树的一个黑色结点,显然左子树的黑色结点少1了,然而右子树又又红色结点,那么我们直接向右子树“借”个红结点来补充黑结点就好啦,此时肯定需要用旋转处理了。如图22所示。

处理:

  • 将S的颜色设为P的颜色
  • 将P设为黑色
  • 将SR设为黑色
  • 对P进行左旋

图22 删除情景2.1.2.1

平衡后的图怎么不满足红黑树的性质?前文提醒过,R是即将替换的,它还参与树的自平衡,平衡后再替换到删除结点的位置,所以R最终可以看作是删除的。另外图2.1.2.1是考虑到第一次替换和自底向上处理的情况,如果只考虑第一次替换的情况,根据红黑树性质,SL肯定是红色或为Nil,所以最终结果树是平衡的。如果是自底向上处理的情况,同样,每棵子树都保持平衡状态,最终整棵树肯定是平衡的。后续的情景同理,不做过多说明了。

删除情景2.1.2.2:替换结点的兄弟结点的右子结点为黑结点,左子结点为红结点
兄弟结点所在的子树有红结点,我们总是可以向兄弟子树借个红结点过来,显然该情景可以转换为情景2.1.2.1。图如23所示。

处理:

  • 将S设为红色
  • 将SL设为黑色
  • 对S进行右旋,得到情景2.1.2.1
  • 进行情景2.1.2.1的处理

图23 删除情景2.1.2.2

删除情景2.1.2.3:替换结点的兄弟结点的子结点都为黑结点
好了,此次兄弟子树都没红结点“借”了,兄弟帮忙不了,找父母呗,这种情景我们把兄弟结点设为红色,再把父结点当作替代结点,自底向上处理,去找父结点的兄弟结点去“借”。但为什么需要把兄弟结点设为红色呢?显然是为了在P所在的子树中保证平衡(R即将删除,少了一个黑色结点,子树也需要少一个),后续的平衡工作交给父辈们考虑了,还是那句,当每棵子树都保持平衡时,最终整棵总是平衡的。

处理:

  • 将S设为红色
  • 把P作为新的替换结点
  • 重新进行删除结点情景处理

图24 情景2.1.2.3

删除情景2.2:替换结点是其父结点的右子结点
好啦,右边的操作也是方向相反,不做过多说明了,相信理解了删除情景2.1后,肯定可以理解2.2。

删除情景2.2.1:替换结点的兄弟结点是红结点
处理:

  • 将S设为黑色
  • 将P设为红色
  • 对P进行右旋,得到情景2.2.2.3
  • 进行情景2.2.2.3的处理

图25 删除情景2.2.1

删除情景2.2.2:替换结点的兄弟结点是黑结点
删除情景2.2.2.1:替换结点的兄弟结点的左子结点是红结点,右子结点任意颜色
处理:

  • 将S的颜色设为P的颜色
  • 将P设为黑色
  • 将SL设为黑色
  • 对P进行右旋

图26 删除情景2.2.2.1

删除情景2.2.2.2:替换结点的兄弟结点的左子结点为黑结点,右子结点为红结点
处理:

  • 将S设为红色
  • 将SR设为黑色
  • 对S进行左旋,得到情景2.2.2.1
  • 进行情景2.2.2.1的处理

图27 删除情景2.2.2.2

删除情景2.2.2.3:替换结点的兄弟结点的子结点都为黑结点
处理:

  • 将S设为红色
  • 把P作为新的替换结点
  • 重新进行删除结点情景处理


图28 删除情景2.2.2.3

综上,红黑树删除后自平衡的处理可以总结为:

  1. 自己能搞定的自消化(情景1)
  2. 自己不能搞定的叫兄弟帮忙(除了情景1、情景2.1.2.3和情景2.2.2.3)
  3. 兄弟都帮忙不了的,通过父母,找远方亲戚(情景2.1.2.3和情景2.2.2.3)

哈哈,是不是跟现实中很像,当我们有困难时,首先先自己解决,自己无力了总兄弟姐妹帮忙,如果连兄弟姐妹都帮不上,再去找远方的亲戚了。这里记忆应该会好记点~

最后再做个习题加深理解(请不熟悉的同学务必动手画下):

***习题2:请画出图29的删除自平衡处理过程。

习题2



写在后面

耗时良久,终于写完了~自己加深了红黑树的理解的同时,也希望能帮助大家。如果你之前没学习过红黑树,看完这篇文章后可能还存在很多疑问,如果有疑问可以在评论区写出来,我会尽自己所能解答。另外给大家推荐一个支持红黑树在线生成的网站,来做各种情景梳理很有帮助:在线生成红黑树。(删除操作那个把替代结点看作删除结点思路就是我自己在用这个网站时自己顿悟的,我觉得这样讲解更容易理解。)

少了代码是不是觉得有点空虚?哈哈,后续我会写关于Java和HashMap和TreeMap的文章,里面都有红黑树相关的知识。相信看了这篇文章后,再去看Java和HashMap和TreeMap的源码绝对没难度!

最后来看下思考题和习题的答案吧。


思考题和习题答案

*思考题1:黑结点可以同时包含一个红子结点和一个黑子结点吗?*
答:可以。如下图的F结点:

*习题1:请画出图15的插入自平衡处理过程。*
答:

*习题2:请画出图29的删除自平衡处理过程。*
答:

大文件排序

1. 如何对一个20GB的文件进行排序

内存肯定没有20GB大,所以不可能采用传统排序法。但是可以将文件分成许多块,每块xMB,针对每个块各自进行排序,存回文件系统。然后将这些块逐一合并,最终得到全部排好序的文件。

外排序的一个例子是外归并排序(External merge sort),它读入一些能放在内存内的数据量,在内存中排序后输出为一个顺串(即是内部数据有序的临时文件),处理完所有的数据后再进行归并。比如,要对900MB的数据进行排序,但机器上只有100 MB的可用内存时,外归并排序按如下方法操作:

读入100 MB的数据至内存中,用某种常规方式(如快速排序、堆排序、归并排序等方法)在内存中完成排序。

将排序完成的数据写入磁盘。

重复步骤1和2直到所有的数据都存入了不同的100 MB的块(临时文件)中。在这个例子中,有900 MB数据,单个临时文件大小为100 MB,所以会产生9个临时文件。 读入每个临时文件(顺串)的前10 MB( = 100 MB / (9块 + 1))的数据放入内存中的输入缓冲区,最后的10 MB作为输出缓冲区。(实践中,将输入缓冲适当调小,而适当增大输出缓冲区能获得更好的效果。)

执行九路归并算法,将结果输出到输出缓冲区。一旦输出缓冲区满,将缓冲区中的数据写出至目标文件,清空缓冲区。一旦9个输入缓冲区中的一个变空,就从这个缓冲区关联的文件,读入下一个10M数据,除非这个文件已读完。这是“外归并排序”能在主存外完成排序的关键步骤,因为“归并算法”(merge algorithm)对每一个大块只是顺序地做一轮访问(进行归并),每个大块不用完全载入主存。