--------------------------------------------------------------------------------
標(biāo)題: B-tree查找函數(shù)
作者: 葉飛虎
日期: 2011.04.19
--------------------------------------------------------------------------------
在 B-tree 中搜索鍵值，結(jié)點(diǎn)內(nèi)可以使用二分查找，若要查找指定范圍內(nèi)數(shù)據(jù)與查找鍵值
相比相對(duì)要復(fù)雜一點(diǎn)。
現(xiàn)給出查找指定范圍內(nèi)第一項(xiàng)和最后一項(xiàng)數(shù)據(jù)的示例代碼：
1 // B-tree 的項(xiàng)
2 typedef struct
3 {
4 long Key; // 鍵值
5 void* Link; // 子結(jié)點(diǎn)或數(shù)據(jù)
6 } TBTItem, *PBTItem;
7
8 // B-tree 的結(jié)點(diǎn)
9 typedef struct
10 {
11 Byte Count; // 項(xiàng)數(shù)[1..維數(shù)]
12 bool IsLeaf; // 是否為葉子結(jié)點(diǎn)
13 TBTItem Items[100]; // 項(xiàng)列表(假設(shè) B-tree 維度為 100)
14 } TBTNode, *PBTNode;
15
16 // 查找范圍內(nèi)的第一項(xiàng)并返回序號(hào)(注: AFrom < ATo)
17 TBTNode* FindFirstItem(TBTNode* ARoot, long AFrom, long ATo,
18 bool AIsInc, long& AIndex)
19 {
20 // 初始化
21 bool boolRet = false;
22 TBTNode* pNode = ARoot;
23 TBTNode* pNext = NULL;
24 long intNext = 0;
25 long intBegin, intEnd, intMid, intKey;
26
27 // 循環(huán)查找層
28 while (pNode != NULL)
29 {
30 // 初始化(注: pNode->Count >= 1)
31 intEnd = pNode->Count - 1;
32 intBegin = 0;
33
34 // 結(jié)點(diǎn)內(nèi)二分查找
35 while (intBegin <= intEnd)
36 {
37 intMid = (intBegin + intEnd) >> 1;
38 intKey = pNode->Items[intMid].Key;
39 if (intKey < AFrom)
40 intBegin = intMid + 1;
41 else
42 {
43 intEnd = intMid - 1;
44 if (intKey == AFrom)
45 {
46 intBegin = intMid;
47 break;
48 }
49 }
50 }
51
52 // 判斷是否為葉結(jié)點(diǎn)
53 AIndex = intBegin;
54 if (pNode->IsLeaf)
55 {
56 if (intKey != AFrom)
57 {
58 if (AIndex != pNode->Count)
59 {
60 boolRet = (pNode->Items[AIndex].Key <= ATo);
61 break;
62 }
63 }
64 else if (AIsInc)
65 {
66 boolRet = true;
67 break;
68 }
69 else if (AIndex < pNode->Count - 1)
70 {
71 AIndex++;
72 boolRet = (pNode->Items[AIndex].Key <= ATo);
73 break;
74 }
75
76 // 下一結(jié)點(diǎn)項(xiàng)
77 if (pNext == NULL)
78 break;
79 else
80 {
81 pNode = (TBTNode*)pNext->Item[intNext].Link;
82 pNext = NULL;
83 }
84 }
85 else
86 {
87 // 校正索引
88 if (AIndex == pNode->Count)
89 AIndex = pNode->Count - 1;
90 else if (intKey == AFrom)
91 {
92 if (AIndex < pNode->Count - 1)
93 {
94 intNext = AIndex + 1;
95 pNext = (pNode->Items[intNext].Key <= To) ? pNode : NULL;
96 }
97 }
98 else if (AIndex == 0)
99 pNext = NULL;
100 else
101 {
102 intNext = AIndex--;
103 pNext = (pNode->Items[intNext].Key <= To) ? pNode : NULL;
104 }
105
106 // 子結(jié)點(diǎn)
107 pNode = (TBTNode*)pNode->Item[AIndex].Link;
108 }
109 }
110
111 // 返回結(jié)果
112 return boolRet ? pNode : NULL;
113 }
114
115 // 查找范圍內(nèi)的最后一項(xiàng)并返回序號(hào)(注: AFrom < ATo)
116 TBTNode* FindLastItem(TBTNode* ARoot, long AFrom, long ATo,
117 bool AIsInc, long& AIndex)
118 {
119 // 初始化
120 bool boolRet = false;
121 TBTNode* pNode = ARoot;
122 long intBegin, intEnd, intMid, intKey;
123
124 // 循環(huán)查找層
125 while (pNode != NULL)
126 {
127 // 初始化(注: pNode->Count >= 1)
128 intEnd = pNode->Count - 1;
129 intBegin = 0;
130
131 // 結(jié)點(diǎn)內(nèi)二分查找
132 while (intBegin <= intEnd)
133 {
134 intMid = (intBegin + intEnd) >> 1;
135 intKey = pNode->Items[intMid].Key;
136 if (intKey < ATo)
137 intBegin = intMid + 1;
138 else
139 {
140 intEnd = intMid - 1;
141 if (intKey == ATo)
142 {
143 intBegin = intMid;
144 break;
145 }
146 }
147 }
148
149 // 判斷是否為葉結(jié)點(diǎn)
150 AIndex = intBegin;
151 if (pNode->IsLeaf)
152 {
153 if ((intKey == ATo) && AIsInc)
154 boolRet = true;
155 else if (AIndex > 0)
156 {
157 AIndex--;
158 boolRet = (pNode->Items[AIndex].Key >= AFrom);
159 }
160
161 break;
162 }
163 else
164 {
165 // 校正索引
166 if ((intKey == ATo) && AIsInc)
167 ;
168 else if (AIndex > 0)
169 AIndex--;
170 else
171 break;
172
173 // 子結(jié)點(diǎn)
174 pNode = (TBTNode*)pNode->Item[AIndex].Link;
175 }
176 }
177
178 // 返回結(jié)果
179 return boolRet ? pNode : NULL;
180 }
181
posted on 2011-05-22 12:00
Kyee Ye 閱讀(348)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
技巧雜集