红黑树和2-3树的关系及溯源

红黑树原理分析参考书目:《算法(第四版)》RobertSedgewick红黑树的起源红黑树的起源来源于一个叫做2-3查找树的东西2-3查找树2-3查找树中拥有两种结点,2度结点和3度结点,这两种结点同时构成了2-3查找树,这种查找树具有一定的平衡性2-3查找树的例子拿3度结点EJ举例,其中的3度结点

#数据结构  

红黑树学习笔记

红黑树学习笔记红黑树的概念红黑树是一种二叉查找树,也是一种特殊的平衡二叉树,因为没有AVL这种很严苛的平衡条件,所以平衡的程度没有像AVL一样非常的极致,但是进行操作的效率要比AVL要高。红黑树就像魔方一样,有各种情况,我们看到某一种情况就可以套公式进行变换,达到想要的目的红黑树的规则/性质1.每一

#数据结构  

AVL平衡二叉树

AVL平衡二叉树学习笔记平衡二叉树平衡二叉树是一种特殊的排序二叉树,它的性质如下:一棵二叉排序树,它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。正因为它有如下性质,它在大多数情况下比二叉排序树要矮的多,查找效率也高得多平衡二叉树的实现方式有很多,比如说红

#数据结构  

哈夫曼树与文件压缩笔记

哈夫曼树哈夫曼编码哈夫曼编码是一种变长的编码,数据的编码因其使用频率而长短不一,使用频率高的数据编码较短,使用频率高的数据编码较长。哈夫曼树的构造算法哈夫曼树的定义最优二叉树带权路径长度WPL最小的二叉树称为哈夫曼树构造哈夫曼树将有权值的叶节点从大到小排成一个有序的序列将权值最小的两个节点作为一个新

#数据结构  

数据结构笔记--树

数据结构学习笔记---树树的基本概念树的基本术语度:一个节点拥有子树的数量高度/深度:约定根节点的高度为3,每增加一层高度加1二叉树的直径:根到叶子节点的一条最长路径,路径长度是树的高度减1森林:m棵互不相交树的集合树的抽象数据类型ADTTree<T>{booleanisEmpty()/

#数据结构  

KMP算法学习笔记

基于链表的KMP算法模式串pattern需要匹配的串称为模式串需求分析查找首个与pattern匹配的子表DoubleNode<T>search(DoublyList<T>pattern)数据结构的声明publicclassDoublyList<T>extendsO

#数据结构  

矩阵的压缩存储

矩阵的压缩存储笔记矩阵需要压缩存储的原因因为矩阵中零元素过多,用二维数组存储非常浪费空间,所以我没需要压缩存储矩阵的压缩存储方法我们使用一个线性表来存储每一行的数据,线性表中存储的是一个表的引用,例如:链表,循环链表等考虑到效率,我们选用排序线性表如图所示:Triple是一个元组,存储的是一个矩阵中

#数据结构  

堆排序

堆排序堆定义最大堆:每个结点的值都大于或等于其左右孩子结点的值最小堆:每个结点的值都小于或等于其左右孩子结点的值由此可知,最大堆的堆顶是堆中最大的一个值,最小堆的堆顶是堆中最小的一个值我们把要排序的一个序列看作一个完全二叉树的层序遍历序列例如:[99,5,36,7,22,17,92,12,2,19,

#数据结构