首页 > 代码库 > 【好记性不如烂笔头】创建一颗用于快速查找数据的多叉树
【好记性不如烂笔头】创建一颗用于快速查找数据的多叉树
假定现有大量人员需要管理,给每个人分配一个n位数的id,现要求快速查找,于是我们建一颗10叉树来管理这批人的信息,这样查找结果为真时查询次数为n,时间复杂度为常数,可谓是最优解了代码如下:
1 using System; 2 using System.Collections.Generic; 3 using System.Diagnostics; 4 using System.Linq; 5 using System.Text; 6 using System.Threading.Tasks; 7 8 namespace MultiTrees 9 { 10 class Program 11 { 12 static void Main(string[] args) 13 { 14 15 Stopwatch watch = new Stopwatch(); 16 17 /*创建多叉树并存入大量数据并监视插入用时*/ 18 MulTree tree = new MulTree(); 19 watch.Start(); 20 for (long i = 3013101000; i < 3023101171; i++) 21 tree.Insert(i+""); 22 watch.Stop(); 23 Console.WriteLine("添加用时:" + watch.Elapsed.TotalMilliseconds + "ms"); 24 25 /*查询,并记录查询用时*/ 26 watch = new System.Diagnostics.Stopwatch(); 27 watch.Start(); 28 Node result = tree.SearchSingleNode("3013203182"); 29 watch.Stop(); 30 31 Console.WriteLine("查询用时:"+watch.Elapsed.TotalMilliseconds+"ms"); 32 Console.WriteLine("查询到数据学号为:"+result.Data); 33 Console.ReadKey(); 34 35 } 36 } 37 /*多叉树类*/ 38 class MulTree 39 { 40 public int Deepth = 10;/*树的深度,存学号就是学号的长度*/ 41 public Node Root { get; set; }/*根节点*/ 42 public MulTree() 43 { 44 Root = new Node(); 45 } 46 /*插入*/ 47 public bool Insert(string str) 48 { 49 /*先检测插入字符串是否有效*/ 50 int[] array = new int[Deepth]; 51 bool flag=DetectionString(str, ref array); 52 if (!flag) 53 { 54 return false; 55 } 56 /*开始插入,将字符串写入最后节点的data里面*/ 57 Node temp = Root; 58 for (int i = 0; i < array.Length; i++) 59 { 60 if (temp == null) temp = new Node(); 61 if (temp.Childs[array[i]]==null) 62 temp.Childs[array[i]] = new Node(); 63 temp = temp.Childs[array[i]]; 64 } 65 temp.Data =http://www.mamicode.com/ str; 66 67 return true; 68 } 69 /*检测字符串是否有效*/ 70 public bool DetectionString(string str, ref int[] array) 71 { 72 if (str.Length != Deepth) return false; 73 char[] strArray = str.ToArray<char>(); 74 int[] intArray = new int[Deepth]; 75 for (int i = 0; i < strArray.Length; i++) 76 { 77 bool flag = int.TryParse(strArray[i] + "", out intArray[i]); 78 if (!flag) return false; 79 } 80 array = intArray; 81 return true; 82 } 83 /*查找,返回查找到的节点*/ 84 public Node SearchSingleNode(string str) 85 { 86 /*检测字符串是否是有效的学号*/ 87 int[] array = new int[Deepth]; 88 bool flag = DetectionString(str, ref array); 89 if (!flag) 90 { 91 return null; 92 } 93 94 /*开始查询*/ 95 Node result = Root; 96 for (int i = 0; i < array.Length; i++) 97 { 98 if (result.Childs[array[i]] == null) 99 return null;100 result = result.Childs[array[i]];101 }102 return result;103 }104 }105 /*节点类*/106 class Node107 {108 public Node[] Childs;109 public string Data{get;set;}110 public Node()111 {112 Childs = new Node[10];113 for (int i = 0; i < Childs.Length; i++)114 Childs[i] = null;115 }116 }117 }
可以看到一千万的数据查询也不过用时0.2毫秒,速度非常快……这样可以快速获取想要获取的数据是否存在,即使是我国16亿人民的18位身份证号,也只需要18次的比对就可以得出结果,当然这样会消耗大量的内存……这个,就暂时不是我关心的了。
2016-10-08 16:02:08
【好记性不如烂笔头】创建一颗用于快速查找数据的多叉树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。