Tag: 数据结构
113 total results found
压缩算法的基础（下）：赫夫曼编码及其应用
上篇文章我们介绍了赫夫曼树的定义和构建，当然，赫夫曼不会闲到为了转化下成绩等级专门实现赫夫曼树，当年，他研究赫夫曼树是为了解决远距离...
压缩算法的基础（上）：赫夫曼树及其构建
今天我们继续分享二叉树的一些应用：赫夫曼树。 我们日常使用压缩和解压软件的频率可谓是非常高，而最基本的压缩算法 —— 赫夫曼编码，...
解决 TopK 问题的利器（下）：堆排序及其应用
堆排序 上篇分享我们介绍了堆的定义及其构建，这篇教程我们来分享堆排序及其应用，堆排序的过程其实就是不断删除堆顶元素的过程。如果构建...
解决 TopK 问题的利器（上）：堆和堆的构建
什么是堆 堆是一种特殊的二叉树，具备以下特性： 堆是一个完全二叉树 每个节点的值都必须大于等于（或小于等于）其左右孩子节点的...
红黑树的动态平衡实现原理分析
插入节点 红黑树规定，插入的节点必须是红色的。而且，二叉排序（查找）树中新插入的节点都是放在叶子节点上。首先，我们来看两种最简单的...
红黑树的特性和算法复杂度
前面几篇分享中我们陆续介绍了平衡二叉树的定义、实现原理、构建过程演示以及对应的实现代码，我们提到平衡二叉树是最理想的二叉排序树，性能...
平衡二叉树（AVL）的实现代码和算法复杂度
下面我们将上一篇分享中演示的平衡二叉树构建示例转化为 PHP 代码。 节点类 我们还是使用二叉链表来实现二叉树的存储，对应的节点...
平衡二叉树的构建实现过程演示
我们在上一篇文章中分享了平衡二叉树的定义和实现原理，这一节我们来演示如何通过代码实现平衡二叉树，最后分析下平衡二叉树的算法复杂度。 ...
平衡二叉树（AVL）的定义和实现原理
引子 上一篇我们介绍了二叉排序树，并且提到理想情况下，二叉排序树的插入、删除、查找时间复杂度都是 O(logn)，非常高效，而且它...
二叉排序（查找）树的定义及实现
为什么要引入二叉排序树 我们前面已经介绍了很多数据结构，比如数组、链表、散列表等，数组查找性能高，但是插入、删除性能差，链表插入、...
PHP 字符串匹配函数 strstr 底层实现原理剖析
PHP 提供的字符串匹配函数多是单模式匹配，因此大多通过 KMP 算法实现，我们以 strstr 函数为例，简单对底层实现源码进行剖...
字符串匹配算法之 Trie 树的定义、实现及应用
介绍完树和二叉树的基本数据结构和算法之后，我们接着之前没讲完的字符串匹配算法。 Trie 树的定义 Trie 树，也叫「前缀树」...
字符串匹配算法之 KMP 算法
KMP 算法可以说是字符串匹配算法中最知名的算法了，KMP 算法是根据三位作者（D.E.Knuth，J.H.Morris 和 V.R...
字符串匹配算法之 BF 算法
今天开始，我们将花三篇文章的篇幅由浅及深地介绍几个字符串匹配算法，首先从最简单的字符串匹配算法 —— BF 算法说起，BF 是 Br...
PHP 数组底层实现原理（二）
数组的初始化 数组的初始化主要是针对 HashTable 成员的设置，初始化时并不会立即分配 arData 的内存，插入第一个元素...