js實(shí)現(xiàn)紅黑樹(shù)

UsherChen 發(fā)布于2019-08-23 14:25 / 2464人閱讀

摘要：概述樹(shù)在前端的重要性就不言而喻了，隨處可見(jiàn)，，，，有時(shí)候前后端交互中也會(huì)收到具有遞歸性質(zhì)的結(jié)構(gòu)數(shù)據(jù)，需要注意一點(diǎn)的是中雖然出現(xiàn)了和數(shù)據(jù)結(jié)構(gòu)，但其實(shí)現(xiàn)和其它語(yǔ)言例如中底層實(shí)現(xiàn)不同，在的中其實(shí)現(xiàn)基于，利用空間換時(shí)間的思想，畢竟查找起來(lái)而紅黑樹(shù)。

概述

樹(shù)在前端的重要性就不言而喻了，隨處可見(jiàn)，vdom，dom tree，render tree，有時(shí)候前后端交互中也會(huì)收到具有遞歸性質(zhì)的tree結(jié)構(gòu)數(shù)據(jù)，需要注意一點(diǎn)的是es6中雖然出現(xiàn)了set和map數(shù)據(jù)結(jié)構(gòu)，但其實(shí)現(xiàn)和其它語(yǔ)言（例如java中）底層實(shí)現(xiàn)不同，在chrome的 v8中其實(shí)現(xiàn)基于hash，利用空間換時(shí)間的思想，畢竟查找起來(lái)hash O(1)而紅黑樹(shù)O(LgN)。但是紅黑樹(shù)作為一種經(jīng)典且重要的數(shù)據(jù)結(jié)構(gòu)，綜合優(yōu)勢(shì)比較好，curd操作以及空間消耗在大量數(shù)據(jù)下優(yōu)勢(shì)就體現(xiàn)出來(lái)了。

js實(shí)現(xiàn)

const RED = true;
const BLACK = false;
class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.left = null;
        this.right = null;
        this.color = RED;
    }
}

class RBT {
    constructor() {
        this.root = null;
        this.size = 0;
    }
    isRed(node) {
        if (!node) return BLACK;
        return node.color;
    }
    // 左旋 右紅左黑
    leftRotate(node) {
        let tmp = node.right;
        node.right = tmp.left;
        tmp.left = node;
        tmp.color = node.color;
        node.color = RED;
        return tmp;
    }
    // 右旋轉(zhuǎn) 左紅左子紅
    rightRoate(node) {
        let tmp = node.left;
        node.left = tmp.right;
        tmp.right = node;
        tmp.color = node.color;
        node.color = RED;
        return tmp;
    }
    // 顏色翻轉(zhuǎn)
    flipColors(node) {
        node.color = RED;
        node.left.color = BLACK;
        node.right.color = BLACK;
    }
    add(key, value) {
        this.root = this.addRoot(this.root, key, value);
        this.root.color = BLACK; // 根節(jié)點(diǎn)始終是黑色
    }
    addRoot(node, key, value) {
        if (!node) {
            this.size++;
            return new Node(key, value);
        }
        if (key < node.key) {
            node.left = this.addRoot(node.left, key, value);
        } else if (key > node.key) {
            node.right = this.addRoot(node.right, key, value);
        } else {
            node.value = value;
        }
        if (this.isRed(node.right) && !this.isRed((node.left))) {
            node = this.leftRotate(node);
        }
        if (this.isRed(node.left) && this.isRed((node.left.left))) {
            node = this.rightRoate(node);
        }
        if (this.isRed(node.left) && this.isRed(node.right)) {
            this.flipColors(node);
        }
        return node;
    }
    isEmpty() {
        return this.size == 0 ? true : false;
    }
    getSize() {
        return this.size;
    }
    contains(key) {
        let ans = "";
        !(function getNode(node, key) {
            if (!node || key == node.key) {
                ans = node;
                return node;
            } else if (key > node.key) {
                return getNode(node.right, key);
            } else {
                return getNode(node.right, key);
            }
        })(this.root, key);
        return !!ans;
    }
    // bst前序遍歷(遞歸版本)
    preOrder(node = this.root) {
        if (node == null) return;
        console.log(node.key);
        this.preOrder(node.left);
        this.preOrder(node.right);
    }
    preOrderNR() {
        if (this.root == null) return;
        let stack = [];
        stack.push(this.root);
        while (stack.length > 0) {
            let curNode = stack.pop();
            console.log(curNode.key);
            if (curNode.right != null) stack.push(curNode.right);
            if (curNode.left != null) curNode.push(curNode.left);
        }
    }
    // bst中序遍歷
    inOrder(node = this.root) {
        if (node == null) return;
        this.inOrder(node.left);
        console.log(node.key);
        this.inOrder(node.right);
    }
    // bst后續(xù)遍歷
    postOrder(node = this.root) {
        if (node == null) return;
        this.postOrder(node.left);
        this.postOrder(node.right);
        console.log(node.key);
    }
    // bsf + 隊(duì)列的方式實(shí)現(xiàn)層次遍歷
    generateDepthString1() {
        let queue = [];
        queue.unshift(this.root);
        while (queue.length > 0) {
            let tmpqueue = []; let ans = [];
            queue.forEach(item => {
                ans.push(item.key);
                item.left ? tmpqueue.push(item.left) : "";
                item.right ? tmpqueue.push(item.right) : "";
            });
            console.log(...ans);
            queue = tmpqueue;
        }
    }
    minmun(node = this.root) {
        if (node.left == null) return node;
        return this.minmun(node.left);
    }
    maximum(node = this.root) {
        if (node.right == null) return node;
        return this.maximum(node.right);
    }
}

let btins = new RBT();
let ary = [5, 3, 6, 8, 4, 2];

ary.forEach(value => btins.add(value));
btins.generateDepthString1();
// ///////////////
//      5       //
//    /        //
//   3     8    //
//  /    /     //
// 2  4  6      //
// ///////////////
console.log(btins.minmun());  // 2
console.log(btins.maximum()); // 8

圖解