JS 实现位图(Bitset)数据结构

位图数组中每个元素在内存中占用1位,所以可以节省存储空间,在索引,数据压缩等方面有广泛应用。
我们使用类型化数组Uint8Array储存位图,数组中每一个元素占8个字节所以最大值是255。关键是寻找偏移量,index>>3 右移三位相当于除8。可以找到对应的数组元素,1 << (index % 8) 找到位对应数组元素的哪一个字节。最后通过按位判断该为1或0。

判断存在时:使用按位与&(只有两个操作数相应的比特位都是1时,结果才为1)
修改某项:使用按位或|

Typescript代码如下:

export class Bitmap {
    private bin: Uint8Array;

    constructor(size: number) {
        this.bin = new Uint8Array(new ArrayBuffer((size >> 3) + 1));
    }

    public get(index: number): boolean {
        const row = index >> 3;
        const bit = 1 << (index % 8);
        return (this.bin[row] & bit) > 0;
    }

    public set(index: number, bool: boolean = true) {
        const row = index >> 3;
        const bit = 1 << (index % 8);
        if (bool) {
            this.bin[row] |= bit;
        } else {
            this.bin[row] &= (255 ^ bit);
        }
    };

    public fill(num: number = 0) {
        this.bin.fill(num);
    }

    public flip(index: number) {
        const row = Math.floor(index / 8);
        const bit = 1 << (index % 8);
        this.bin[row] ^= bit;
    }
}

二叉搜索树

特点

  1. 左子树的节点 < 根节点 < 右子树节点
  2. 没有重复节点

查找

    search(key, node = this.roots) {
        if (node) {
            if (key < node.key) {
                return this.search(node.left, key);
            } else if (key > node.key) {
                return this.search(node.right, key);
            } else {
                return true;
            }
        } else {
            return false;
        }
    }

插入和删除

插入很简单,就是在树的最底层寻找一个合适的位置。

   insert(key) {
        let newNode = {
            key: key,
            left: null,
            right: null
        };
        if (!this.roots) {
            this.roots = newNode;
        } else {
            this.insertNode(this.roots, newNode);  // 从根节点开始
        }
        return this;  // 链式操作
    };

    insertNode(node, newNode) {
        if (newNode.key < node.key) {
            if (!node.left) {
                node.left = newNode;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else if(newNode.key > node.key){
            if (!node.right) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        }else{
            return false;  //不能有键值相等的节点
        }
    }

删除比较复杂,要根据子节点情况分三类进行操作:
1.如果没有子节点直接删除
2.如果有一个子节点那么将孩子提升到被删除元素的位置
3.如果有两个子节点则需要用被删除节点的右子树中最小节点替换,如下图所示:

屏幕快照 2017-05-11 下午6.06.00.png

    remove(key, node = this.roots) {
        if (node === null) {
            return false;
        }

        if (key < node.key) {
            node.left = this.remove(key, node.left);
            return node;
        } else if (key > node.key) {
            node.right = this.remove(key, node.right);
            return node;
        } else {
            //如果没有子节点直接删除
            //如果有一个子节点那么将孩子提升到被删除元素的位置
            if (node.left === null && node.right === null) {
                node = null;
                return node;
            } else if (node.left === null) {
                node = node.right;
                return node;
            } else if (node.right === null) {
                node = node.left;
                return node;
            } else {
                //如果有两个子节点
                console.log(node)
                let aux = this.findMinNode(node.right);  //在右子树中向左到尽头找到最小节点
                node.key = aux.key;
                node.right = this.remove(aux.key, node.right);
                return node;
            }
        }
    }

    findMinNode(node) {
        while (node && node.left) {
            node = node.left;
        }
        return node;
    }

复杂度

搜索、插入、删除的复杂度等于树高。
同样一棵二叉搜索树,全部由插入生成的和经过插入和删除的两棵树就不一样。树高的期望为 {O(log n)},最坏 {O(n)}

正因为这种随机性,特别是当插入有序的节点时,树就会退化成线性表,所以我们还会对二叉搜索树进行优化,让其拥有最好的最坏复杂度。你听说过的红黑树、AVL树就是解决这一问题而出现的,下篇文章我们会介绍。

二叉树的遍历

链表,栈和队列等线性数据结构的遍历很简单,但是到了非线性遍历方法多了很多。
主要有两类:深度优先遍历(DFS)和广度优先遍历(BFS)。这里你可能会想到,不应该是前序、中序、后序遍历吗。没错,这些其实就是深度优先遍历的几种方式。而广度优先遍历的访问原则“先上后下-先左后右”,所以不像深度优先优先遍历,根据访问节点方式的不同有不同方式。

image from dsacpp.3rd_edn-min.png

深度优先遍历

1.递归实现

// 前序递归遍历T
void preOrder(TreeNode *root) {
    if(root == NULL)
        return;
    cout << root->val << endl;
    preOrder(root->left);
    preOrder(root->right);
}

2.非递归实现

void preOrder(TreeNode *root) {
    if(root == NULL)
        return;

    stack<TreeNode *> stk;
    stk.push(root);
    while(!stk.empty()) {
        TreeNode *pNode = stk.top();
        stk.pop();
        cout << pNode->val << endl;
        if(pNode->right != NULL)
            stk.push(pNode->right);
        if(pNode->left != NULL)
            stk.push(pNode->left);
    }
}

广度优先遍历

// 用queue实现的BFS  
void BFS(Node *pRoot) {  
    if (pRoot==NULL)  
        return;  
  
    queue<Node*> Q;
    Q.push(pRoot);  
  
    while(!Q.empty()) {    
        Node *node = Q.front();
        cout<<node->nVal<<"->";  
        if (node->pLeft!=NULL) {  
            Q.push(node->pLeft);  
        }  
  
        if (node->pRight!=NULL) {  
            Q.push(node->pRight);  
        }  
  
        Q.pop();  
    }  
  
    cout<<endl;  
}