基数树






基数树的一个例子


在计算机科学中，基数树，或称Patricia trie/tree，或crit bit tree，压缩前缀树，是一种更节省空间的Trie（前缀树）。对于基数树的每个节点，如果该节点是唯一的子樹的话，就和父节点合并。



应用


基数树可用来构建关联数组。
用于IP 路由。
信息检索中用于文本文档的倒排索引。



操作


基数树支持插入、删除、查找操作。查找包括完全匹配、前缀匹配、前驱查找、后继查找。所有这些操作都是O(k)复杂度，其中k是所有字符串中最大的长度。



查找




示例：基数树中查找一个字符串



















































  • 查

  • 论

  • 编



计算机科学中的树

二叉树


  • 二叉查找树（BST）

  • 笛卡尔树

  • MVP树

  • Top tree（英语：Top tree）

  • T树
自平衡二叉查找树


  • AA树

  • AVL树

  • 左倾红黑树

  • 红黑树

  • 替罪羊树

  • 伸展树

  • 树堆

  • 加权平衡树
B树


  • B+树

  • B*树

  • Bx树

  • UB树

  • 2-3树

  • 2-3-4树

  • (a,b)-树

  • Dancing tree（英语：Dancing tree）

  • H树
堆


  • 二叉堆

  • 二项堆

  • 斐波那契堆

  • 左偏树

  • 配对堆

  • 斜堆

  • Van Emde Boas tree（英语：Van Emde Boas tree）
Trie


  • 后缀树

  • 基数树

  • 三叉查找树

  • X-快速前缀树

  • Y-快速前缀树

  • AC自动机

二叉空间分割（BSP）树


  • 四叉树

  • 八叉树


  • k-d树

  • 隐式k-d树

  • VP树
非二叉树


  • 指数树

  • 融合树

  • 区间树

  • PQ树

  • Range tree（英语：Range tree）

  • SPQR树

空间数据分割树


  • R树

  • R*树

  • R+树

  • X树

  • M树

  • 线段树

  • 可持久化线段树

  • 希尔伯特R树

  • 优先R树
其他树


  • 散列日历

  • 散列树

  • Finger tree（英语：Finger tree）

  • 顺序统计树

  • Metric tree（英语：Metric tree）

  • Cover tree（英语：Cover tree）

  • BK树

  • Doubly chained tree（英语：Doubly chained tree）

  • iDistance（英语：iDistance）

  • Link-cut tree（英语：Link-cut tree）

  • Log-structured merge-tree（英语：Log-structured merge-tree）

  • 树状数组







-

Popular posts from this blog

澳門輕軌系統

Image
本文或本章節是關於未來的公共运输建設或計划。 未有可靠来源的臆測內容可能會被移除，現時內容可能與竣工情況有所出入。 本文或本章節是關於澳門未來的建設或計畫 。 它可能包含推测的性质的信息，可能與竣工情況有所出入。 body.skin-minerva .mw-parser-output table.infobox caption{text-align:center} 澳門輕軌系統 葡萄牙語： Sistema de Metro Ligeiro de Macau 英语： Macau Light Rapid Transit System (Macau LRT System) 概覽 營運地區   澳門 服務類型 輕軌運輸 车站总数 氹仔線：11個 澳門半島線：10個 起訖站点 關閘 正線总数 3條 主要路線 海洋 - 氹仔碼頭 路線等級 輕軌 主要車站 蓮花口岸、 機場、氹仔碼頭 技術數據 路線長度 氹仔線：9.3公里 軌道標準 膠輪路軌系統 动力方式 第三軌供電 750V 車輛基地 計劃興建總數11個： 澳門半島6個，氹仔5個 运营信息 營運時期 氹仔線：預計於2019年 运营单位 港鐵（澳門）（2019年－2023年） 澳門輕軌股份有限公司（2023年後） 網站 http://www.git.gov.mo 路線圖 各期工程完成後的路線走向（模擬）圖 澳門輕軌系統（未來） 圖例 關閘 馬場北 馬場東 青洲 A區車廠 筷子基 新城A區01 紅街市
Read more

水泉澳邨

Image
水泉澳邨 //upload.wikimedia.org/wikipedia/commons/6/66/Shui_Chuen_O_Estate_Overview_2016.jpg 水泉澳邨航拍圖 房屋機構 香港房屋委員會 所屬地區 沙田區 屋邨類別 租住屋邨 入伙年份 2015年至2017年 樓宇座數 18 單位數目 11123 單位面積 151.23-397.73 呎（ft²） 住戶數目 10900 （截至2017年6月30日情況） 認可人口 28200 （截至2017年6月30日情況） 水泉澳邨內貌（2016年3月） 水泉澳邨 （ 英语： Shui Chuen O Estate ） [1] 是香港房屋委員會轄下的一個公共屋邨。全邨共分4期興建及管理，第1及2期樓宇由水泉澳邨辦事處管轄，第3及4期樓宇則由水泉澳邨辦事處分處管轄。項目編號為ST41，但已列入擴展市區配屋區內，位於香港新界沙田區水泉澳（沙田第52區）博泉街1號，已經興建18座樓高25至30層依山而建的住宅樓宇，共提供11,123個出租公屋單位，可容納人口逾29,000多人及水泉澳廣場，場內設有59個商舖及一個整體出租街市。水泉澳邨將設有行人天橋和升降機塔，接通博康邨和港鐵馬鞍山綫的沙田圍站；邨內亦設有公共交通交匯處及泊車位，方便居民出行。 整個項目於2015年4月至2017年3月分階段落成。整個項目由房屋署總建築師（1）負責總體設計；而詳細設計則拆細並以外判服務合約方式，第1及4期判給了周林建築師有限公司；第2A期（明泉樓、社會福利大樓、巴士總站、天橋及商場）及第3期（茂泉、林泉、修泉及竹泉樓）判給了興業建築師事務所有限公司及第2B期（月泉及映泉樓）判給了李景勳、雷煥庭建築師事務所；而第2C期（城泉及河泉樓）則由房屋署自行負責細部設計。全邨的總承建商是中國建築工程（香港）有限公司。 水泉澳邨共有18座出租公屋大樓，共分4期興建，第1期於2015年4月至7月底分2個階段完工，第2期在2016年3月至11月底分4個階段完工，第3期已於2017年2月完工交樓，第4期的嶺泉樓早已於2016年8月完工入伙，而餘下的崇泉、山泉及峻泉樓則由20
Read more

Indian Forest Service

Image
Indian Forest Service Service Overview Preceding service Imperial Forest Service (1864 to 1935) Year of Constitution 1966 Country India Staff College Indira Gandhi National Forest Academy (IGNFA), Dehradun, Uttarakhand Cadre Controlling Authority Ministry of Environment, Forests and Climate Change Legal personality Governmental: Government service General nature Administration of Forest and Wildlife resources Cadre strength 3131 (2182 Direct Recruits and 949 Promotion Posts) Website ifs.nic.in Service Chief Director General of Forests Siddhanth Das, IFS (1982 Batch, Odisha Cadre) [1] Head of the All India Civil Services Cabinet Secretary Pradeep Kumar Sinha, IAS Indian Forest Service (भारतीय वन सेवा) [2] is one of the three All India Services of the Government of India. The other two All India Services being the Indian Administrative Service (IAS) and the Indian Police Service (IPS). [3] [4] [5] It was constituted in
Read more