发表于 | 分类于 ， ， | | 阅读次数
概述 AVL树得名于它的发明者G.M. Adelson-Velsky和E.M. Landis,它是最先发明的自平衡二叉查找树. 在AVL树中任何节点的两个子树的高度最大差别为一.并且,查找、插入、删除等操作在平均和最坏情况下都是O(log n). AVL树的基本操作都与二叉查找树的算法一致,只有在插 ...
阅读全文 »

发表于 | 分类于 ， ， | | 阅读次数
红黑二叉查找树是2-3查找树的简单表示方式,它的代码量并不大,并且保证了平衡性.阅读本文前需先了解 《Algorithms,4th Edition》读书笔记-2-3查找树 概述 红黑树是一种自平衡的二叉查找树,它的基本思想是用标准的二叉查找树(完全由2-节点构成)和一些额外的信息(替换3-节点) ...
阅读全文 »

发表于 | 分类于 ， ， | | 阅读次数
概述 由于二叉查找树的性能与树的高度(即根节点到底部节点的深度)相关,因此当高度较大时,二叉查找树的性能就会下降.为了更高效的性能,平衡查找树应运而生,它能保证无论键的插入顺序如何,树的高度都将是总键数的对数. 2-3查找树就是平衡树的一种. 性质 2-3查找树允许树中的一个节点保存多个键.我们可以 ...
阅读全文 »

发表于 | 分类于 ， ， | | 阅读次数
概述 二叉查找树是一颗有序的二叉树,它有以下性质: 若任意节点的左子树不为空,则左子树上所有节点的值均小于它的根节点的值. 若任意节点的右子树不为空,则右子树上所有节点的值均大于它的根节点的值. 可以将每个链接看做指向另一颗二叉查找树,而这棵树的根节点就是被指向的节点. 没有键值相等的 ...
阅读全文 »

发表于 | 分类于 ， | | 阅读次数
最近在读<>时,了解到了很多常用的排序算法,故写一篇读书笔记记录下这些排序算法的思路和实现. 冒泡排序 冒泡排序是一种非常简单的初级排序算法,它每次比较相邻的两个元素,如果顺序错误就进行交换.由于最小的元素是经由不断交换慢慢浮到顶端的,所以叫做冒泡排序. 冒泡排序对n个元素需要O(n ...
阅读全文 »

发表于 | 分类于 ， ， | | 阅读次数
什么是链表? 链表是一种常见的基础数据结构(数组也是基础数据结构),它是一种递归的数据结构,由一系列节点(Node)组成,节点含有一个存储数据的数据域和一个指向下一个节点地址位置的引用. 链表是线性表的一种,但是它的物理存储结构是非连续、 非顺序的,元素的逻辑顺序是通过节点之间的链接确定的. 数据结 ...
阅读全文 »

发表于 | 分类于 ， ， | | 阅读次数
对象的创建   在Java程序运行过程中无时无刻都有对象被创建出来.在语言层面上,创建对象通常仅仅是一个new关键字而已,而在虚拟机中,创建一个对象不像只需要new一下那么简单了.   以下为虚拟机中对象创建的过程(仅限于普通Java对象,不包括数组和Clas ...
阅读全文 »

发表于 | 分类于 ， ， | | 阅读次数
概述   对于C/C++程序员来说需要自己负责每一个对象生命开始到终结的维护.而对于Java程序员来说,则可以在Java虚拟机自动内存管理机制的帮助下,不需要为每一个new的对象去写delete/free代码,由虚拟机管理内存可以让我们把注意力放在实现业务逻辑上.  & ...
阅读全文 »