Patricia树介绍

概述

小编本想在网上找一篇合适的文章来介绍这个Patricia树的，但找了半天，没发现一个合适的。尤其很多地方直接把标准的trie当成了Patricia树，这样很容易受到勿扰。
思来想去，小编打算自己大概介绍下这个树了。

看该文前，Patricia树是标准trie的改进，因此，建议大家先看看另一篇文章：浅谈标准Trie树（字典树）

什么是Patricia树

对标准Trie树有过了解后，聪明的你会发现标准Trie树有如下缺点：

1. 标准Trie树给每个字符分配一个结点，如果某个字符串没有公共结点，那就变成，一个字符串每个字符占用一个空间，长此下去，资源量费
2. 容易遭到黑客拒绝服务攻击。

为了解决这些问题，Patricia树悄然而生，它和标准Trie树最大的区别就是，对于其中的结点，如果该节点是唯一的儿子的话，就和父节点合并。
标准trie树再讲一遍也没意思，下面这张图是小编在网上找到的一张很能标明Patricia树结构的图，应该是一目了然吧？

公共结点与标准Trie树一样，叶子结点处，都是兄弟。也就是说，除了叶子结点，每个结点都有左孩子和右孩子。