01trie树

基本介绍

01Trie树其实就是Trie树的一种运用,普通的Trie树只是用来存储和查找字符串,而01Trie树只是将存储的字母变成了数组的二进制每一位,即0和1.

01Trie树主要是用来求解异或最值问题。

01Trie树特点如下:

1、一般01Trie树最多只有32层,因为最多31位二进制位,其中每个节点的两条边都表示某一位是0还是1,某条路径从根节点到叶子结点就得到了一个二进制数。

2、从上到下分别为某个数二进制的最高位和最低位。

3、可通过贪心的策略来寻找与x异或结果最大(最小)的数,即优先找和x的二进制的未处理的最高位值不同(相同)的边对应的点,这样保证结果最大。

阅读更多...
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信