20-数据结构-红黑树（数据结构中最难的部分了，万老说暂时看不懂很正常，的确我到现在也没真正弄明白这代码）

和AVL 树一样，红黑树也是一个自平衡二叉搜索树。

在红黑树中，每个节点都遵循以下规则：

(1) 顾名思义，每个节点不是红的就是黑的；

(2) 树的根节点是黑的；

(3) 所有叶节点都是黑的（用NULL 引用表示的节点）；

(4) 如果一个节点是红的，那么它的两个子节点都是黑的；

(5) 不能有两个相邻的红节点(一个红节点不能有红的父节点或子节点)；

(6) 从给定的节点到它的后代节点（NULL 叶节点）的所有路径包含相同数量的黑色节点。

万老的课件:

红黑树建立在基本的二叉搜索树的基础之上，所以需要把之前的二叉搜索树代码复制过来：

// 二叉搜索树代码
// 树中每个存储数据的地方叫元素节点，所以要创建一个节点的类
class Node{
    constructor(key){ // 这里的key不像是栈或者队列里面的索引，树的key直接对应的就是节点所存储的数据值
        this.key = key // 存储节点值
        this.left = null // 索引，指向左侧子节点，就像双向链表，链表是上下结构（指针域指向上和下），树是左右结构（指向左和右）
        this.right = null // 索引，指向右侧子节点
    }
}

//二叉搜索树类
class BinarySearchTree{
    constructor(){
        this.root = null // 二叉树的根节点，默认值为null，初始化
    }

    insert(key){ // 往二叉树里面插入新的值
        if(!this.root){ // 如果根节点没有值，那么就插到二叉树的根节点中
            this.root = new Node(key)
        }else{ // 如果根节点已经有了值，做判断，比较插入的子节点的值与父节点的值得大小，来决定是左侧子节点还是右侧子节点
            // 调用往某个节点插入值的方法
            this.insertNode(this.root,key) // this.root是因为要每次插入新值的时候，要从根节点开始做比较大小的判断并插入值
        }
    }

    insertNode(node,key){ // 往某个节点插入一个值，node表示父节点，key表示子节点的值，子节点的值要和父节点的值比较后决定左右侧
        // 这么写的原因是为了在已经有了大量数据的时候，能够递归地调用
        if(key < node.key){ // 如果待插入的值 比 父节点的值小，插左边
            // 还要细分，如果该父节点的左边已经有了一个子节点（因为不可能每次都是插入根节点的子节点，万一有很多层），那么就要判断
            if(node.left){ // 该父节点左侧已有子节点，待插入的值 就要成为 该子节点 的 子节点（不确定有多少层，所以要递归）
                this.insertNode(node.left,key) // 递归调用往某个节点插入值的方法，这次是左侧子节点的值与待插入值比较大小
            }else{ // 如果该父节点左侧没有子节点，直接插入成为该父节点的子节点
                node.left = new Node(key)
            }
        }else{ // 大于或是等于插右边同样右侧子节点也要进行递归判断
            if(node.right){ // 该父节点右侧已有子节点，待插入的值 就要成为 该子节点 的 子节点（不确定有多少层，所以要递归）
                this.insertNode(node.right,key) // 递归调用往某个节点插入值的方法，这次是右侧子节点的值与待插入值比较大小
            }else{ // 如果该父节点右侧没有子节点，直接插入成为该父节点的子节点
                node.right = new Node(key)
            }
        }
    }

    min(){ // 查询整个二叉树的最小值，同样需要一个递归方法，因为无法得知哪个节点才是最小值
        return this.minNode(this.root) // 返回 从根节点开始递归判断查找最小值的函数方法 的 返回值
    }
    // 注意区分min方法和minNode方法的区别，一个是查找整个树的最小值，一个是从某个节点开始往下的最小值（不一定是整个树的最小值）
    minNode(node){ // 从某个指定的节点开始 递归地判断查找最小值方法，node表示传入的节点
        let current = node // 将每一次当前传入的节点保存在变量中
        while(current && current.left){ // 当 当前节点存在值 并且 当前节点的左侧子节点也存在值时，说明还有更小的值
            current = current.left // 就将左侧子节点的变成当前节点，继续进行循环比较
        }
        // 否则直接进行返回，左侧没有子节点就表明当前节点就是最小值所在节点
        return current
    }

    max(){ // 查询整个二叉树的最大值，同样需要一个递归方法，因为无法得知哪个节点才是最小值
        return this.maxNode(this.root) // 返回 从根节点开始递归判断查找最小值的函数方法 的 返回值
    }
    // 注意区分max方法和maxNode方法的区别，一个是查找整个树的最大值，一个是从某个节点开始往下的最大值（不一定是整个树的最大值）
    maxNode(node){ // 从某个指定的节点开始 递归地判断查找最大值方法，node表示传入的节点
        let current = node // 将每一次当前传入的节点保存在变量中
        while(current && current.right){ // 当 当前节点存在值 并且 当前节点的右侧子节点也存在值时，说明还有更大的值
            current = current.right // 就将右侧子节点的变成当前节点，继续进行循环比较
        }
        // 否则直接进行返回，右侧没有子节点就表明当前节点就是最大值所在节点
        return current
    }

    // 中序遍历
    inOrderTraverse(cb){ // 接收一个回调函数，中序遍历排序
        this.inOrderTraverseNode(this.root,cb) // 从根节点开始中序遍历排序
    }

    inOrderTraverseNode(node,cb){ // 中序遍历递归方法
        if(node){ // 当该节点存在的时候才做遍历操作
            this.inOrderTraverseNode(node.left,cb)
            cb(node.key) 
            this.inOrderTraverseNode(node.right,cb) // 递归
        }
    }

    // 先序遍历
    preOrderTraverse(cb){ // 接收一个回调函数，先序遍历数据的结构
        this.preOrderTraverseNode(this.root,cb) // 从根节点开始先序遍历
    }

    preOrderTraverseNode(node,cb){ // 先序遍历递归方法
        if(node){ // 当该节点存在的时候才做遍历操作
            cb(node.key) // 把遍历到的值放到回调函数进行操作
            this.preOrderTraverseNode(node.left,cb)
            this.preOrderTraverseNode(node.right,cb) // 递归
        }
    }

    // 后序遍历
    postOrderTraverse(cb){ // 接收一个回调函数，后序遍历
        this.postOrderTraverseNode(this.root,cb) // 从根节点开始后序遍历排序
    }

    postOrderTraverseNode(node,cb){ // 后序遍历递归方法
        if(node){ // 当该节点存在的时候才做遍历操作
            this.postOrderTraverseNode(node.left,cb)
            this.postOrderTraverseNode(node.right,cb) // 递归
            cb(node.key)  
        }
    }

    // 查找功能
    searchKey(key){
        return this.searchNode(this.root,key)
    }

    searchNode(node,key){ // 递归方法
        // 先判断树里面有没有东西
        if(node){ // 树中必须有节点才能进行搜索
            // 再判断值的大小，决定从哪边搜
            if(key < node.key){ // 如果传入的值比当前节点的值小，继续搜索左侧子节点
                return this.searchNode(node.left,key)
            }else if(key > node.key){ // 如果传入的值比当前节点的值大，继续搜索右侧子节点
                return this.searchNode(node.right,key)
            }else{ // 既不是大于也不是小于那就是搜到了
                return true
            }
        }else{ // 如果节点都不存在那就不用搜了
            return false
        }
    }

    // 删除功能
    removeKey(key){
        this.root = this.removeNode(this.root,key)
    }

    removeNode(node,key){
        if(node){ // 树里面有节点存在才能删
            if(key < node.key){ // 从左侧开始搜
                node.left = this.removeNode(node.left,key)
                return node // 返回拼接后的节点
            }else if(key > node.key){ // 从右侧开始搜
                node.right = this.removeNode(node.right,key)
                return node // 返回拼接后的节点
            }else{ // 找到了要删除的对象
                // 第一种情况：待删除的节点下面左右两侧都有子节点
                if(node.left && node.right){

                    let target = this.minNode(node.right) // 将待删除节点的右侧子节点的所有子节点中最小的子节点找出来，即最小孙子节点
                    node.key = target.key // 最小孙子节点替补到被删除节点的位置上
                    node.right = this.removeNode(node.right,key) // 把那个找来做替补的最小孙子节点从原来的孙子位置上删掉

                    return node
                }

                // 第二种情况：待删除节点左侧或者右侧有子节点
                if(node.left || node.right){
                    if(node.left){ // 如果待删除节点左侧有子节点，左侧子节点替代被删除节点
                        node = node.left
                    }
                    if(node.right){ // 同理
                        node = node.right
                    }
                    return node // 返回替代后的节点
                }

                // 第三种情况：待删除节点就是一个叶节点
                node = null
                return node
            }
        }else{
            return null
        }
    }

    // 修改功能
    updateKey(key,key1){
        return this.updateNode(this.root,key,kye1)
    }

    updateNode(node,key,key1){ // 递归方法
        // 先判断树里面有没有东西
        if(node){ // 树中必须有节点才能进行搜索
            // 再判断值的大小，决定从哪边搜
            if(key < node.key){ // 如果传入的值比当前节点的值小，继续搜索左侧子节点
                return this.updateNode(node.left,key,key1)
            }else if(key > node.key){ // 如果传入的值比当前节点的值大，继续搜索右侧子节点
                return this.updateNode(node.right,key,key1)
            }else{ // 既不是大于也不是小于那就是搜到了
                node.key = key1
                return true
            }
        }else{ // 如果节点都不存在那就不用搜了
            return false
        }
    }
}

// 以下开始才是真正的红黑树代码
const Color = {
    RED:1,
    BLACK:2
}

class RedBlackNode extends Node{ // 红黑树节点继承自节点
    constructor(key) {
        super(key)
        this.key = key
        this.color = Color.RED // 默认给红色（因为只有红色才能触发后面的平衡逻辑，所以就是要它不平衡或者容易不平衡），红色不行的话后面再改成黑的
        this.parent = null // 用于记录父节点的指针，根据父节点的颜色和自己的颜色来判断是否需要平衡
    }

    isRed(){ // 判断该节点是否为红色
        return this.color === Color.RED
    }
}

class RedBlackTree extends BinarySearchTree{ // 红黑树继承自搜索树
    constructor() {
        super()
        this.root = null
    }

    insert(key){ // 插入新节点（接收的值）
        if(!this.root){ // 如果根节点为空
            this.root = new RedBlackNode(key) // 插入的值就变成根节点的值
            this.root.color = Color.BLACK // 生成的根节点必定是黑的
        }else{
            let newNode = this.insertNode(this.root,key) // 从根节点开始递归判断新节点应该插在什么地方
            this.fixTree(newNode) // 新节点插入完成之后修复平衡整棵树
        }
    }

    insertNode(node, key) { // 这是插入新节点所用到的逻辑与递归方法
        if(key < node.key){ // 待插入节点的值小于父节点的值，插左边
            // 再判断父节点的左侧是否已经存在了节点
            if(node.left){ // 如果父节点左侧有子节点，那待插入的节点就继续递归与该左侧子节点进行比较判断（这是递归入口）
                return this.insertNode(node.left,key)
            }else{ // 如果父节点左侧没有子节点，那么就直接插入成为左侧子节点（这是递归出口）
                node.left = new RedBlackNode(key) // 左侧生成新的红黑树子节点
                node.left.parent = node // 记录新插入生成的左侧子节点的父节点为最后一次递归比较的node节点
                return node.left // 最后将插入完成的节点返回回去
            }
        }else{ // 否则就是待插入节点的值大于或等于父节点的值，插右边
            // 再判断父节点的右侧是否已经存在了节点
            if(node.right){ // 如果右侧已经存在子节点，那待插入的节点就继续递归与该右侧子节点进行比较判断（这是递归入口）
                return this.insertNode(node.right,key)
            }else{ // 如果父节点右侧没有子节点，那么就直接插入成为右侧子节点（这是递归出口）
                node.right = new RedBlackNode(key) // 右侧生成新的红黑树子节点
                node.right.parent = node // 记录新插入生成的右侧子节点的父节点为最后一次递归比较的node节点
                return node.right // 最后将插入完成的节点返回回去
            }
        }
    }

    fixTree(node){ // 插完新节点之后进行修复红黑树
        // 因为不知道要修复到什么时候，就用while无限进行修复，直到平衡为止
        while(node && node.parent && node.parent.isRed() && node.isRed()){ // 该节点存在，该节点的父节点存在（即不能是根节点），该节点的父节点为红色，该节点为红色（不能有两个相邻的红节点，所以需要进行修复操作）
            let parent = node.parent // 预存该节点的父节点
            let grandParent = parent.parent // 预存该节点的祖父节点

            // 接下来就要做两步：颜色要重新设置 以及 分析是否平衡
            // 分情况：父节点是左侧
            if(grandParent && grandParent.left === parent){ // 祖父节点存在并且祖父节点的左侧子节点全等于父节点
                const uncle = grandParent.right // 叔父节点，因为父亲节点在左侧，所以叔父节点在右侧
                // 如果父节点的颜色被修改，那么和父节点同一级的叔父节点的颜色也要修改
                
                if(uncle && uncle.isRed()){ // 这里一个小细节，把uncle放在uncle.isRed前面，因为前面为真才会返回后面的，
                    // 如果uncle不存在，访问它的属性就会报错，所以为了防止出现报错，先判断uncle是否存在
                    
                    // 叔父节点存在代表着父一级节点是平衡的，所以新插入的节点无论插左边还是右边，高度差最多为1
                    // 叔父节点也是红色的，那么只需要重新填色
                    grandParent.color = Color.RED // 祖父节点变色
                    parent.color = Color.BLACK // 父节点变
                    uncle.color = Color.BLACK // 叔父节点变
                    node = grandParent
                }else{ // 否则就是uncle节点不存在
                    // 新插入节点是右侧子节点的时候
                    // 旋转保证平衡 向左转
                    if(node === parent.right){
                        this.rotationRR(parent)
                        node = parent // 父节点替换到原先子节点的位置
                        parent = node.parent // 祖父节点替换到原先父节点的位置
                    }

                    // 否则新插入节点是左侧子节点的时候
                    // 旋转保证平衡 向右转
                    this.rotationLL(grandParent)
                    parent.color = Color.BLACK
                    grandParent.color = Color.RED
                    node = parent
                }
            }else{ // 否则父节点就是右侧
                const uncle = grandParent.left // 叔父节点在左侧

                if(uncle && uncle.isRed()){ // 这里一个小细节，把uncle放在uncle.isRed前面，因为前面为真才会返回后面的，
                    // 如果uncle不存在，访问它的属性就会报错，所以为了防止出现报错，先判断uncle是否存在
                    
                    // 叔父节点存在代表着父一级节点是平衡的，所以新插入的节点无论插左边还是右边，高度差最多为1
                    // 叔父节点也是红色的，那么只需要重新填色
                    grandParent.color = Color.RED // 祖父节点变色
                    parent.color = Color.BLACK // 父节点变
                    uncle.color = Color.BLACK // 叔父节点变
                    node = grandParent
                }else{ // 否则就是uncle节点不存在
                    // 节点是右侧子节点的时候
                    // 旋转保证平衡 向左转
                    if(node === parent.left){
                        this.rotationLL(parent)
                        node = parent
                        parent = node.parent
                    }

                    // 节点是左侧子节点的时候
                    // 旋转保证平衡 向右转
                    this.rotationRR(grandParent)
                    parent.color = Color.BLACK
                    grandParent.color = Color.RED
                    node = parent 
                }
            }
        }
    }

    rotationLL(node){ // 情况：祖父节点的左侧是父节点，父节点的左侧是被插入的子节点（注意：这里的参数node是祖父节点）
        // 此时就需要进行向右的单旋转
        let temp = node.left
        node.left = temp.right
        if(temp.right && temp.right.key){ // 如果父节点的右侧有节点并且该节点有值
            temp.right.parent = node
        }
        temp.parent = node.parent

        if(!node.parent){
            this.root = temp
        }else{
            if(node === node.parent.left){
                node.parent.left = temp
            }else{
                node.parent.right = temp
            }
        }
        temp.right = node
        node.parent = temp
    }

    rotationRR(node){ // 情况：祖父节点的右侧是父节点，父节点的右侧是被插入的子节点（注意：这里的参数node是祖父节点）
        // 此时就需要进行向左的单旋转
        let temp = node.right
        node.right = temp.left
        if(temp.left && temp.left.key){
            temp.left.parent = node
        }
        temp.parent = node.parent

        if(!node.parent){
            this.root = temp
        }else{
            if(node === node.parent.left){
                node.parent.left = temp
            }else{
                node.parent.right = temp
            }
        }
        temp.left = node
        node.parent = temp
    }
}
复制代码