一种基于有序二叉树的高效优化索引树.pdf

14 4 Vol. 14 No. 4 2004 4 Microcomputer Development Apr . 2004 吴海辉, 吴建国 ( 安徽大学计算机系, 安徽 合肥 230039) : , , , , , , , , : ; trie- ; : T P3016 : A : 1005- 3751( 2004) 04- 0018- 04 An Effici ent Optimi zed Trie- Tree Based on Ordered Binary Tree WU Haihui, WU Jian uo ( Dept. of Computer Sci. , Anhui Univ. , Hefei 230039, China) Abstract : Encountered strin retrieval w hile pro rammin an input method editor of Chinese character. T hus have proposed an efficient op timized trie- tree based on ordered binary tree. By usin special structure as th e trie- tree node s memory structure and puttin the trie- tree in a byte lo ic array, ot an optimized trie- tree w hich avoided null pointer. The optimized trie- tree have th e merits of low memory space and rapid tree traversal. In this paper, also presented the al orithms of buildin and retrieval of the optimized trie- tree in detail. Key words:binary tree; trie- tree; optimized trie- tree 0 1 b ; i, , 2 i ; ASCII n, 3 n [ 1] ; 4 ! ∀ trie- , trie- , ASCII ( , trie- , ) ( [ 2] 1 trie- , ) 1 trie- 1 trie- , , , : a. , , b. , trie-