【好記性不如爛筆頭】建立一顆用于快速查找資料的多叉樹

假定現有大量人員需要管理，給每個人配置設定一個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 = 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 Node
107     {
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

黑夜給了我黑色的眼睛，我卻用它尋找光明