首页 > 代码库 > 【好记性不如烂笔头】创建一颗用于快速查找数据的多叉树

【好记性不如烂笔头】创建一颗用于快速查找数据的多叉树

假定现有大量人员需要管理,给每个人分配一个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

【好记性不如烂笔头】创建一颗用于快速查找数据的多叉树