数据结构-Radix-Tree

发表于 分类于 阅读次数： 本文字数： 969 阅读时长 ≈ 1 分钟

Radix Tree - 基数树

radix tree用于表示一种空间优化的tree. 假如树中的一个节点是父节点的唯一子节点，那么该节点将会与父节点进行合并 radix tree的边沿edges可以是一个或者多个元素
元素个数不是太多，但是元素之间通常有很长的相同前缀时很适合采用radix tree存储
Golang的web框架gin使用radix tree作为路由查找的算法.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# gin/gin.go

// method -> HTTP Method {GET,PUT,POST,DELETE}
func (engine *Engine) addRoute(method, path string, handlers HandlersChain) {
	assert1(path[0] == '/', "path must begin with '/'")
	assert1(method != "", "HTTP method can not be empty")
	assert1(len(handlers) > 0, "there must be at least one handler")

	debugPrintRoute(method, path, handlers)

  // 每一个method对应一颗radix tree
	root := engine.trees.get(method)
	if root == nil {
    // 如果获取不到method对应的树，就创建
		root = new(node)
		root.fullPath = "/"
		engine.trees = append(engine.trees, methodTree{method: method, root: root})
	}
	root.addRoute(path, handlers)

	// Update maxParams
	if paramsCount := countParams(path); paramsCount > engine.maxParams {
		engine.maxParams = paramsCount
	}