每个项目具有多个键的树数据结构

Question

我正在使用 node js 开发一个显示在线用户列表的聊天应用程序。每个用户都有以下属性：

ipv4,rank,score,登录时间

访问用户时使用ipv4

应按照此排序策略列出用户：

排名较高的用户应该在列表的顶部。
如果用户排名相等，则得分最高的用户应该排在高排名用户之后的列表顶部。
如果用户评分相等，则登录时间少的用户排在高分用户之后，排名靠前

例如：

1。登录 userA (ipv4:1.1.1.1, rank:0, score:3000, loginTime:1631966424070)

列表：[userA]

2。登录 userB (ipv4:2.2.2.2, rank:1, score:2000, loginTime:1631966424080)

列表：[userB, userA]

3。登录 userC (ipv4:3.3.3.3, rank:1, score:1000, loginTime:1631966424090)

列表：[userB, userC, userA]

4。登录 userD (ipv4:4.4.4.4, rank:0, score:3000, loginTime:1631966424100)

列表：[用户 B、用户 C、用户 A、用户 D]

访问示例：

获取用户(ipv4:3.3.3.3) -> return userC

有很多用户，我使用functional-red-black-tree数据结构来提高性能。在这个数据结构中，每个项目都有一个键和一个值。这棵树的构造函数接受一个比较器函数——类似数组排序比较器——带有两个参数，每个参数都是键，作为参数。

我定义了 user 如下：

class Key {
    constructor(ipv4, rank, score, loginTime) {
        this.ipv4 = ipv4;
        this.rank = rank;
        this.score = score;
        this.loginTime = loginTime;
    }
}

class OnlineUser {

    constructor(ipv4, rank, score, loginTime, name, avatar, bio, gender) {
        this.key = new Key(ipv4, rank, score, loginTime);
        this.name = name;
        this.avatar = avatar;
        this.bio = bio;
        this.gender = gender;
    }
}
module.exports = { OnlineUser, Key };

我用这样的比较函数定义了树：

const createTree = require('functional-red-black-tree');

var tree = createTree((userAKey, userBKey) => {
    if (userAKey.ipv4 == userBKey.ipv4) return 0;
    if (userAKey.rank < userBKey.rank) return 1;
    if (userAKey.rank > userBKey.rank) return -1;
    if (userAKey.score < userBKey.score) return 1;
    if (userAKey.score > userBKey.score) return -1;
    if (userAKey.loginTime < userBKey.loginTime) return -1;
    if (userAKey.loginTime > userBKey.loginTime) return 1;
});

并添加用户：

tree = tree.insert(user.key, user);

问题： 所有用户都以正确的顺序添加。但是要访问或删除或...用户通常 returned undefined:

const OnlineUser = require('./model/OnlineUser').OnlineUser;
const Key = require('./model/OnlineUser').Key;

for (let i = 0; i < 1000; i++) {
    let user = new OnlineUser(i, rand(), rand(), rand(), '', '', '', 1);
    tree = tree.insert(user.key, user);
}
console.log(tree.get(new Key(10, 0, 0, 0)));

function rand() {
    return Math.floor(Math.random() * 100);
}

我认为这个问题是因为比较器函数使用不同的值进行比较和相等。

在我看来的解决方案是对所有密钥进行哈希处理，并将其变成一个哈希如下的密钥：

function hash(ipv4, rank, score, loginTime){
    let hashCode;
    //How to implement?
    return hashCode;
}

如果 ipv4 与其他键相同，则无论其他键如何，哈希值都相同。
如果ipv4不相等，rank大于其他，则hash值会大于其他（除了前面的条件）而不考虑其他键。
如果ipv4不等于rank等于其他score 大于其他，哈希值将是无论其他键如何，都比其他键大（前面的条件除外）。
如果ipv4不等于rank等于其他score等于别人登录时间小于别人，哈希值将是无论其他键如何，都比其他键大（前面的条件除外）。

Answer 1

在您的 rand 示例中，键 (10, 0, 0, 0) 不匹配是正常的，即使 ipv4=10 在树中的某个位置。这是因为该节点将更像 (10, 66, 35, 19)... 不会遇到，因为树的 ordering 主要基于等级，而不是在 ipv4 上。决定在树中向下钻取的位置将基于等级 (0)，移动到树的左侧，而您要查找的节点可能在右侧（更高等级 66）。

你可以做的是用 Map 伴随树，它将 ipv4 值映射到现有的 Key 实例。所以每次在树中插入的时候，也在那个Map里面添加对应的映射。每次您想查找或删除时，首先通过您拥有的 ipv4 值从该映射中检索 Key 实例，然后将该 Key 实例传递给树的 get 或 remove方法。

这是一个包装器 class，可以实现这种组合。使用您想要包含的任何其他方法对其进行扩展：

const createTree = require('functional-red-black-tree');

class Key {
    constructor(ipv4, rank, score, loginTime) {
        this.ipv4 = ipv4;
        this.rank = rank;
        this.score = score;
        this.loginTime = loginTime;
    }
}

class OnlineUser {
    constructor(ipv4, rank, score, loginTime, name, avatar, bio, gender) {
        this.key = new Key(ipv4, rank, score, loginTime);
        this.name = name;
        this.avatar = avatar;
        this.bio = bio;
        this.gender = gender;
    }
}

class Tree {
    constructor(comparator) {
        this.tree = createTree(comparator);
        this.map = new Map;
    }
    insert(user) {
        this.tree = this.tree.insert(user.key, user);
        this.map.set(user.key.ipv4, user.key);
    }
    get(ipv4) {
        let key = this.map.get(ipv4);
        if (key) return this.tree.get(key);
    }
    remove(ipv4) {
        let key = this.map.get(ipv4);
        if (key) return tree.remove(key);
    }
}

let tree = new Tree((userAKey, userBKey) =>
    userBKey.rank - userAKey.rank ||
    userBKey.score - userAKey.score ||
    userBKey.loginTime - userAKey.loginTime
);

// Insert  some data:
let userA = new OnlineUser("1.1.1.1", 0, 3000, 1631966424070, "userA");
let userB = new OnlineUser("2.2.2.2", 1, 2000, 1631966424080, "userB");
let userC = new OnlineUser("3.3.3.3", 1, 1000, 1631966424090, "userC");
let userD = new OnlineUser("4.4.4.4", 0, 3000, 1631966424100, "userD");

for (let user of [userA, userB, userC, userD]) {
    tree.insert(user);
}

// Make use of the redblack `forEach`:
tree.tree.forEach((key, value) => console.log(value.name))
// Use our own `get` method:
console.log(tree.get("3.3.3.3")); // userC

每个项目具有多个键的树数据结构

Tree data structure with multiple keys for each item

javascript

tree

binary-tree

node.js

data-structures