基数树

基数树

基数树是一种更加节省空间的数据结构,他是字典树的升华,

字典树的缺陷

常常字典树会很深,而不胖,这会导致空间的浪费,因为里面的指针很多,往往我们发现,如下列字典树
稍等片刻!正在将字符数据转化为图形

1
2
3
4
5
graph LR
start((start))--a--> 1((1))
1((1))--b-->2((2))
2((2))--c-->3((end))
2((2))--d-->3((end))

用基数树改进字典树

我们可以通过压缩字符路径为字符串路径,即将长链压缩为一条边。

1
2
3
4
graph LR
start((start))--ab-->2((2))
2((2))--c-->3((end))
2((2))--d-->3((end))

当然你甚至还能这样

1
2
3
graph LR
start((start))--abc-->3((end))
start((start))--abd-->3((end))

这些都是合法的基数树。注意,基数树仍然是字典树,只不过他压缩了路径

用基数树加速IP路由检索

路由检索常常是检索一个01字符串,这时候我们可以通过压缩的方式,每两位压缩、或者三位、四位压缩,能够让查找次数更少,当然这样做可能会牺牲空间,但是他依然是基数树优化的字典树。