前言
红点系统作为游戏内的活动开启、提醒等有着重要的作用，并广泛用于几乎所有类型的游戏中。之前在项目中为了实现红点都是各个业务使用独立逻辑，当有红点之前有父子层级结构时，逻辑就变得非常复杂和难以维护。最近看了几篇前缀树实现红点系统的文章，自己也来尝试实现一个。
效果
这里先上一个gif展示效果。左上角的数值分为左右两部分：左边为节点及其所有子节点的总数值；右边为此节点自身的数值。
前缀树介绍
前缀树或Trie树，是一种哈希树的变种树形数据结构。其核心特征是通过共享字符串的公共前缀减少存储空间和缩短查询时间，查询效率优于传统哈希树。每个节点存储单一字符，子节点字符互不相同，路径构成对应字符串。基本操作包括插入、查找和前缀匹配，节点通常包含标识字段用于标记单词结尾。该结构广泛应用于字符串检索、自动补全、拼写检查、IP路由表以及文本统计排序，被搜索引擎系统用于词频统计与字典序排序。通过构建路径实现快速检索和前缀匹配，节点压缩技术与动态内存管理可优化存储效率。持久化字典树采用数据压缩、并发锁机制和分布式计算框架提升性能，支持多线程构建与查询。 – 百度百科
红点数据节点的数据结构
红点节点作为树的节点，和其介绍的一样，主要由一个字典存储着所有的子节点，其中的key为节点的名字，value为具体的节点。因为红点需要显示具体的数值和便于刷新，所以我增加了节点本身的数值、该节点下所有的数值与父节点，方便显示和根据父节点刷新。节点的代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public class RedDotDataNode
{
private string m_redDotName;
private int m_allRedDotNum;
private int m_redDotNum;
private Action<RedDotDataNode> m_refreshCallBack;
private Dictionary<string, RedDotDataNode> m_RedDotDict = new Dictionary<string, RedDotDataNode>();
private RedDotDataNode m_parentRedDotNode;
private bool m_isSubChange;
}
|
节点的操作
因为游戏内的红点就算消失了，外层的红点也是会继续显示。所以节点不设计删除节点功能，只有对节点数值的增加和减少。
增加节点
增加节点的逻辑比较简单，对于传入的节点，若字典为空直接添加；否则在字典中查询，查询不到直接添加，成功查询则更新，这里为更新其本身红点数量和刷新回调。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| public RedDotDataNode AddRedDot(string redDotPath, string redDotNodeName, int redDotNum,
Action<RedDotDataNode> refreshCallBack)
{
if (m_RedDotDict.Count <= 0)
{
var resultNode = new RedDotDataNode(redDotNodeName, redDotNum, refreshCallBack);
resultNode.m_parentRedDotNode = this;
m_RedDotDict.Add(redDotNodeName, resultNode);
return resultNode;
}
if (m_RedDotDict.TryGetValue(redDotNodeName, out var redDotDataNode))
{
redDotDataNode.AddRedDotNum(redDotNum);
if (refreshCallBack != null)
{
redDotDataNode.SetRefreshCallBack(refreshCallBack);
}
return redDotDataNode;
}
else
{
var resultNode = new RedDotDataNode(redDotNodeName, redDotNum, refreshCallBack);
resultNode.m_parentRedDotNode = this;
m_RedDotDict.Add(redDotNodeName, resultNode);
return resultNode;
}
}
|
减少节点
减少节点只是操作对应节点的红点数值，所以更加简单，直接从字典中查询，若查询到则扣除对应的数值。
1
2
3
4
5
6
7
8
9
10
| public RedDotDataNode SubRedDot(string redDotPath, string redDotNodeName, int redDotNum)
{
if (m_RedDotDict.TryGetValue(redDotNodeName, out var redDotDataNode))
{
redDotDataNode.SubRedDotNum(redDotNum);
return redDotDataNode;
}
return null;
}
|
数值改变刷新
对于每次增加数值的增加和减少，需要更新自身的数值，并且向上刷新所有父节点的数值。减少的逻辑相似，调用对应的Sub函数即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public void RefreshAddRedDotNum(int addNum)
{
if (addNum <= 0)
{
return;
}
AddAllRedDotNum(addNum);
var curNode = this;
curNode.m_refreshCallBack?.Invoke(curNode);
while (curNode.m_parentRedDotNode != null)
{
curNode.m_parentRedDotNode.AddAllRedDotNum(addNum);
curNode.m_parentRedDotNode.m_refreshCallBack?.Invoke(curNode.m_parentRedDotNode);
curNode = curNode.m_parentRedDotNode;
}
}
|
刷新节点下的所有
刷新该节点下的所有节点则为遍历字典，对所有的节点实行递归刷新。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public int RefreshAllRedDotNode()
{
m_allRedDotNum = m_redDotNum;
if (m_RedDotDict.Count <= 0)
{
m_refreshCallBack?.Invoke(this);
return m_allRedDotNum;
}
foreach (var redDotDataNode in m_RedDotDict.Values)
{
if (redDotDataNode == null)
{
continue;
}
m_allRedDotNum += redDotDataNode.RefreshAllRedDotNode();
}
m_refreshCallBack?.Invoke(this);
return m_allRedDotNum;
}
|
红点系统
当红点数据节点实现完成，红点系统已经完成了大部分的功能。红点系统只需要维护一个红点根节点，并对外开放根据路径进行增删查改的接口，就完成了所有功能。
单例
这里我使用了单例模式，类中维护一个红点根节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| public class RedDotSystem
{
private RedDotDataNode m_rootNode;
#region 单例模式
private static RedDotSystem m_Instance;
public static RedDotSystem Instance
{
get
{
if (m_Instance == null)
{
m_Instance = new RedDotSystem();
}
return m_Instance;
}
}
private RedDotSystem()
{
m_rootNode = new RedDotDataNode(RedDotNameDefine.RedDotRoot, 0, null);
}
#endregion
}
|
添加红点
添加节点通过传入一个路径，其中路径的是从顶层往底层的顺序排列，并且每一层使用|字符分割(A|B|C)。通过遍历分割后的字符数组后，每一层都执行添加操作。为了往下遍历到对应的节点，代码这里对应非最后一层使用了0和null占位，对于最后一层才传入真正的数值。在添加完成后，执行刷新逻辑，保证数值正确。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| public void AddRedDotNode(string redDotPath,int redDotNum,Action<RedDotDataNode> refreshCallBack)
{
var redDotSplitName = SplitRedDotPath(redDotPath);
if (redDotSplitName == null || redDotSplitName.Length <= 0)
{
return;
}
RedDotDataNode curRedDotNode = m_rootNode;
for (int i = 0; i < redDotSplitName.Length; i++)
{
string redDotName = redDotSplitName[i];
bool isLast = i >= redDotSplitName.Length - 1;
if (isLast)
{
curRedDotNode = curRedDotNode.AddRedDot(redDotPath,redDotName, redDotNum,refreshCallBack);
}
else
{
curRedDotNode = curRedDotNode.AddRedDot(redDotPath,redDotName,0,null);
}
}
if (redDotNum > 0)
{
curRedDotNode.RefreshAddRedDotNum(redDotNum);
}
}
|
减少红点
减少数值的逻辑与添加类似，都是先遍历分割的字符串到对应的节点。唯一不同的就是因为减少操作对于0数值是不变的，所以维护了一个bool记录是否改变，只有改变是才执行刷新逻辑。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| public void SubRedDotNode(string redDotPath, int redDotNum)
{
if (redDotNum <= 0)
{
return;
}
var redDotSplitName = SplitRedDotPath(redDotPath);
if (redDotSplitName == null || redDotSplitName.Length <= 0)
{
return;
}
RedDotDataNode curRedDotNode = m_rootNode;
for (int i = 0; i < redDotSplitName.Length; i++)
{
if (curRedDotNode == null)
{
return;
}
string redDotName = redDotSplitName[i];
if (i == redDotSplitName.Length - 1)
{
curRedDotNode = curRedDotNode.SubRedDot(redDotPath,redDotName, redDotNum);
}
else
{
curRedDotNode = curRedDotNode.SubRedDot(redDotPath,redDotName,0);
}
}
if (curRedDotNode.GetIsSubChange())
{
curRedDotNode.RefreshSubRedDotNum(redDotNum);
}
}
|
性能分析
对于一个m层的红点路径执行添加和删除操作时，做了三步：
1、路径分割
2、遍历路径，对路径查询
3、更新数值
时间复杂度：第一步分割函数为O(m);第二步遍历路径为O(m),查询因为使用字典为O(1);第三步m层向上更新也为O(m)。所以总体的时间复杂度为O(m)。
空间复杂度：在内存分配上主要集中在第一步的路径分割，因为使用了C#的Split函数，此函数在分割时会为分割的每个字串分配内存，所以m层的红点路径创建了O(m)的数值进行存储。
