哈希表是种数据结构,它可以提供快速的插入操作和查找操作。第一次接触哈希表时,它的优点多得让人难以置信。不论哈希表中有多少数据,插入和删除(有时包括侧除)只需要接近常量的时间即0(1)的时间级。实际上,这只需要几条机器指令。对哈希表的使用者一一人来说,这是一瞬间的事。哈希表运算得非常快,在计算机程序中,如果需要在一秒种内查找上千条记录通常使用哈希表(例如拼写检查器)哈希表的速度明显比树快,树的操作通...点击进入阅读全文

B树的定义

一棵m阶的B树满足下列条件树中每个结点至多有m个孩子。除根结点和叶子结点外,其它每个结点至少有m/2个孩子。根结点至少有2个孩子(如果B树只有一个结点除外)。所有叶结点在同一层,B树的叶结点可以看成一种外部节点,不包含任何信息。有k个关键字(关键字按递增次序排列)的非叶结点恰好有k+1个孩子。看到上面的定义是不是感到十分熟悉,哈哈,是不是和-树的定义是一样的?这个是必须的,因为所谓...点击进入阅读全文

设f(n)为高度为n的平衡二叉树最少含有的节点数,则:f(1) = 1;f(2) = 2; f(3) = 4;f(4) = 7;…这些可以通过画图就能得到,但是当n很大时呢?其实有如下结论:f(n) = f(n-1) + f(n-2) +1,(n>=3)。这个递推结论如何得到的呢?引导问题:求一棵二叉树的节点数目假设一颗二叉树T,其左右子树分别为TL,TR。又假设T的节点数目为F(T),TL,...点击进入阅读全文

     

是什么?

    要了解平衡二叉树,先得了解什么是二叉树?

二叉树定义

在计算机中,二叉树是每一个节点最多有两个子树的结构。通常子树被称作“左子树(left subtree)”“右子树(right subtree)”. 二叉树常被用于实现二叉树查找和二叉堆。

什么是平衡二叉树

     平衡二叉树(Balance Binary Tree)是二叉树的一个进化体,是一个引入平衡概念的二叉树。与...
点击进入阅读全文

树中的叶子结点的个数 计算方法

在学习树的时候经常会遇到计算树中叶子结点的个数的题,比如现在有这样一道题

已知在一棵度为4的树T中,若有20个度为4的结点,10个度为3的结点,1个度为2的结点,10个度为1的结点,则树T的叶子结点的个数为?

解决这道题的思路是列出一个关于各个度的结点的等式,从而根据已知条件算出度为0的结点的个数,下面具体说一下解题方法设树T中的结点个数为n,度为0的结点的个数为n0,...
点击进入阅读全文

树、森林转化二叉树

树转二叉树

分为三个步骤
  • 兄弟+横线树中的每一个结点,如果该结点有兄弟结点,那么就在这几个兄弟结点之间进行连线。
  • 保存长子线对于树中的每一个结点,如果其有多个子节点,保存其第一个子节点的连线,去除其他子节点的连线。
  • 调整位置对每个结点调整一定的位置,使其符合二叉树的标准。
案例将上图中的树转化为二叉树第一步:兄弟+横线第二步:保留长子线第三步:调整位置,横线变斜线

森林转二叉树

森林转二叉树分为三个步骤...
点击进入阅读全文

求nextval数组值的第二种方法
模式串
next值
nextval值
1.第一位的nextval值必定为0,第二位如果于第一位相同则为0,如果不同则为1。       2.第三位的next值,那么将第三位和第一位进行比较,均为a相同则,第三位的nextval值为       3.第四位的next值为2,那么将第四位和第二位进行比较不同,则第四位的nextval值为其next值...
点击进入阅读全文

用一个实际的例子来说明,经历了看懂,看不懂,看懂,看不懂,看懂...后我终于决定把它记下来了。例子字符串为:abaabac首先可以肯定,第一个位置永远位0,第二个位置永远为1.那么可以初始化如下表格
然后求上表中红色的a多对应的值:公式为(a前面的字符串中所有前缀字符与a前面的字符串中所有后缀自付中所有后缀字符相同的字符的最大中长度最长的长度)+1;公式看起来很复杂,一步一步来说明...
点击进入阅读全文

首先简要介绍一下AC自动机:Aho-Corasick automation,该算法在1975年产生于贝尔实验室,是著名的多模匹配算法之一。一个常见的例子就是给出n个单词,再给出一段包含m个字符的文章,让你找出有多少个单词在文章里出现过。要搞懂AC自动机,先得有模式树(字典树)Trie和KMP模式匹配算法的基础知识。KMP算法是单模式串的字符匹配算法,AC自动机是多模式串的字符匹配算法。AC自动机和...点击进入阅读全文

Trie树

    Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。

    Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

    Trie树也有它的缺点,Trie树...

点击进入阅读全文