Shulou(Shulou.com)06/03 Report--

本篇内容主要讲解"如何在C#中使用二叉树实时计算海量用户积分排名"，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习"如何在C#中使用二叉树实时计算海量用户积分排名"吧!

思路解析

关于算法核心思想前面的文章中写的很详细，我不再重复描述，这里只用一个具体示例演示这个过程。假设积分范围是0-5，我们对它不断进行中位分区直到不能分为止，形成如下一棵二叉树：

其中每个树节点包含2个信息：节点范围range[min，max) 和命中数量计数器count ，可以看到叶子节点的range一定是相邻的2个数。

假如现在有一个积分3要插入到树中，该如何操作呢？当前节点从根节点开始，分别判断是否包含于左右子节点，如果包含的话当前节点改为这个子节点，同时计数器加1，然后再次进行相同判断，直到遍历到叶子节点为止，遍历顺序如下：

再依次插入1和4，二叉树的演变情况为：

数据放进去后怎么判断它是排名多少呢？还是从根节点开始，判断它是否包含于左子节点，如果包含的话说明它比右子节点中count个数小（在count名之外），然后再往下一级做同样的判断;如果包含于右子节点那就继续往下判断，直到碰到叶子节点为止。依次累加count最后加上叶子节点占的一位就得到了它在这棵树里的排名，以1为例演示判断步骤（排名为2+1=3）：

好了，一切就绪，只欠代码。

撸码实现

树结构由节点构成，那首先设计一个节点类：

/// /// 树节点对象 /// public class TreeNode { /// /// 节点的最小值 /// public int ValueFrom { get; set; } /// /// 节点的最大值 /// public int ValueTo { get; set; } /// /// 在节点范围内的数量 /// public int Count { get; set; } /// /// 节点高度（树的层级） /// public int Height { get; set; } /// /// 父节点 /// public TreeNode Parent { get; set; } /// /// 左子节点 /// public TreeNode LeftChildNode { get; set; } /// /// 右子节点 /// public TreeNode RightChildNode { get; set; } }树节点的属性主要包含范围值ValueFrom、ValueTo、计数器Count、左子节点LeftChildNode和右子节点RightChildNode，由此组成一个有层次的树结构。然后就是定义我们的树对象了，它的核心字段就是代表源头的根节点：public class RankBinaryTree { /// /// 根节点 /// private TreeNode _root; }根据前面的算法思想，创建树的时候要用积分范围初始化所有节点，这里约定了最小积分为0，通过构造函数传入最大值并创建树结构：/// /// 构造函数初始化根节点 /// /// public RankBinaryTree(int max) { _root = new TreeNode() { ValueFrom = 0, ValueTo = max+1, Height = 1 }; _root.LeftChildNode = CreateChildNode(_root, 0, max / 2); _root.RightChildNode = CreateChildNode(_root, max / 2, max); } /// /// 遍历创建子节点 /// /// /// /// /// private TreeNode CreateChildNode(TreeNode current, int min, int max) { if (min == max) return null; var node = new TreeNode() { ValueFrom = min, ValueTo = max, Height = current.Height + 1 }; node.Parent = current; int center = (min + max) / 2; if (min

< max - 1) { node.LeftChildNode = CreateChildNode(node, min, center); node.RightChildNode = CreateChildNode(node, center, max); } return node; }有了树以后下一步就是往里面插入数据，根据前面介绍的逻辑：/// /// 往树中插入一个值 /// /// public void Insert(int value) { InnerInsert(_root, value); _data.Add(value); } /// /// 子节点判断范围遍历插入 /// /// /// private void InnerInsert(TreeNode node, int value) { if (node == null) return; //判断是否在这个节点范围内 if (value >

= node.ValueFrom && value

< node.ValueTo) { //更新节点总数信息 node.Count++; //更新左子节点 InnerInsert(node.LeftChildNode, value); //更新右子节点 InnerInsert(node.RightChildNode, value); } }下一步提供方法获取指定值在树中的排名：/// /// 从树中获取总排名 /// /// /// public int GetRank(int value) { if (value < 0) return 0; return InnerGet(_root, value); } /// /// 遍历子节点获取累计排名 /// /// /// /// private int InnerGet(TreeNode node, int value) { if (node.LeftChildNode == null || node.RightChildNode == null) return 1; if (value >

= node.LeftChildNode.ValueFrom && value < node.LeftChildNode.ValueTo) { //When this value exists in the left child node, add the total number of right child nodes (indicating how many names this number is after) return node.RightChildNode.Count + InnerGet(node.LeftChildNode, value); } else { //If you are in the right child node, continue to traverse return InnerGet(node.RightChildNode, value); } }

At this point, the core functionality has been achieved. Considering the integral update, we can add node update and deletion methods. Delete is easy, and insert reverse operation on the line, update is easier, delete the old node and calculate the new value can be inserted, the complete code has been uploaded to Github. How efficient is this tree? Let's run a minute and see.

Test, walk.

In the test program, I simulated a scenario with a score range of 0-1000000. This range covers almost 90% of the points in real business. Member systems with more than 1 million points should be relatively rare.

The distribution of the points of the members is also uneven. Generally speaking, the proportion of users with small points is the largest, and the higher the point value, the smaller the proportion of users. In the program, I assume that there are 1 million members, of which 50W user points are within 100, 30W user points are 100-10000, 15W user points are 10000-50000, and 5W user points are above 50000.

The following is the elapsed time for each operation:

It can be seen that this efficiency is not generally fast, and the query time to obtain the ranking is almost negligible. At this time, someone asked, so much data will not eat memory, the following task manager to see the use of trees and not the use of memory:

Operating environment is.NetCore3.0 Console, test host configuration:

1 million data only occupies 130 MB of memory, which is simply sprinkling water on modern computers ~

Be sure to pay attention to thread safety issues when using in business environment!!!

At this point, I believe everyone has a deeper understanding of "how to use binary tree in C#to calculate mass user points ranking in real time," so let's actually operate it! Here is the website, more related content can enter the relevant channels for inquiry, pay attention to us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.