BinaryHashTree.js

class BinaryHashTree {
    constructor() {
        this.root = null;
        this.depth = 0;  // 记录树的当前深度
    }

    // 将数字转换为二进制字符串
    toBinaryString(num) {
        return (num >>> 0).toString(2);
    }

    // 补齐树的深度
    _extendDepth(targetDepth) {
        let current = this.root;
        if (!current) {
            current = { '0': null, '1': null, parent: null };
        }
        // 补齐深度
        for (let i = this.depth; i < targetDepth; i++) {
            current.parent = { '0': current, '1': null, parent: null };
            current = current.parent;
        }
        
        this.root = current;
        this.depth = targetDepth;
    }

    // 插入一个数字到哈希树中
    insert(num) {
        let binaryStr = this.toBinaryString(num);
        
        // 如果树的深度不够，扩展深度
        if (binaryStr.length > this.depth) {
            this._extendDepth(binaryStr.length);
        } else {
            // 如果数字位数小于树的深度，用0补齐
            binaryStr = binaryStr.padStart(this.depth, '0');
        }
        
        if (!this.root) {
            this.root = { '0': null, '1': null, parent: null };
        }
        this._insert(this.root, binaryStr, 0, num);
    }

    // 递归插入节点
    _insert(node, binaryStr, depth, num) {
        if (depth === binaryStr.length) {
            // 叶子节点，添加count和value属性
            node.count = (node.count || 0) + 1;
            node.value = num;
            return;
        }

        const bit = binaryStr[depth];
        if (!node[bit]) {
            // 非叶子节点，只保留必要属性
            node[bit] = { '0': null, '1': null, parent: node };
        }
        this._insert(node[bit], binaryStr, depth + 1, num);
    }

    // 递归查找
    _find(node, binaryStr, depth) {
        if (!node || depth === binaryStr.length) {
            return node;
        }
        return this._find(node[binaryStr[depth]], binaryStr, depth + 1);
    }

    // 查找下一个更大的节点
    _findNext(node) {
        if (!node) return null;
        
        // 如果当前节点有父节点
        if (node.parent) {
            // 如果当前节点是父节点的左子节点，尝试查找父节点的右子树
            if (node.parent['0'] === node && node.parent['1']) {
                return this._findMin(node.parent['1']);
            }
            // 如果当前节点是父节点的右子节点，继续向上查找
            return this._findNext(node.parent);
        }
        return null;
    }

    // 返回大于或等于指定数字的所有数字的迭代器
    *findGreaterOrEqual(num) {
        if (!this.root) return;
        
        const targetBinary = this.toBinaryString(num);
        const paddedBinary = targetBinary.padStart(this.depth, '0');
        
        // 找到目标数字所在的节点
        let currentNode = this._find(this.root, paddedBinary, 0);
        
        // 如果没找到目标数字，从树的最小值开始查找
        if (!currentNode || currentNode.count === undefined) {
            currentNode = this._findMin(this.root);
            while (currentNode && currentNode.value < num) {
                currentNode = this._findNext(currentNode);
            }
        }
        
        if (!currentNode) {
            return;
        }
        
        // 遍历所有大于等于目标数字的节点
        while (currentNode) {
            for (let i = 0; i < currentNode.count; i++) {
                yield currentNode.value;
            }
            currentNode = this._findNext(currentNode);
        }
    }

    // 查找一个数字的出现次数
    find(num) {
        let binaryStr = this.toBinaryString(num);
        if (binaryStr.length > this.depth) return 0;
        binaryStr = binaryStr.padStart(this.depth, '0');
        let node = this._find(this.root, binaryStr, 0);
        return node && node.count !== undefined ? node.count : 0;
    }

    // 删除一个数字的一个实例
    delete(num) {
        // 类型检查
        if (typeof num !== 'number') return false;
        
        let binaryStr = this.toBinaryString(num);
        if (binaryStr.length > this.depth) return false;
        binaryStr = binaryStr.padStart(this.depth, '0');
        let node = this._find(this.root, binaryStr, 0);
        if (!node || node.count === undefined || node.count === 0) return false;
        
        node.count--;
        if (node.count === 0) {
            // 向上清理节点
            let current = node;
            while (current.parent) {
                const parent = current.parent;
                // 清除父节点对当前节点的引用
                if (parent['0'] === current) {
                    parent['0'] = null;
                } else {
                    parent['1'] = null;
                }
                
                // 如果父节点还有其他子节点，停止清理
                if (parent['0'] || parent['1']) {
                    break;
                }
                current = parent;
            }
            
            // 如果删除到了根节点
            if (current === this.root && !current['0'] && !current['1']) {
                this.root = null;
            }
        }
        return true;
    }

    // 查找最小的数字节点
    _findMin(node) {
        if (!node) return null;
        
        // 如果当前节点有value属性，说明是叶子节点
        if (node.hasOwnProperty('value')) {
            return node;
        }
        
        // 优先选择'0'路径
        if (node['0']) {
            const result = this._findMin(node['0']);
            if (result !== null) return result;
        }
        
        // 如果'0'路径没有找到，尝试'1'路径
        if (node['1']) {
            return this._findMin(node['1']);
        }
        
        return null;
    }

    // 获取树中最小的数字
    findMin() {
        if (!this.root) return null;
        const node = this._findMin(this.root);
        return node ? node.value : null;
    }

    // 从小到大返回所有值
    *all() {
        if (!this.root) return;
        let currentNode = this._findMin(this.root);
        while (currentNode) {
            for (let i = 0; i < currentNode.count; i++) {
                yield currentNode.value;
            }
            currentNode = this._findNext(currentNode);
        }
    }
}

// 导出类
module.exports = BinaryHashTree;