自平衡树-AVL树
8.4 自平衡树BST树会存在一个问题:取决于你添加的节点数,树的一条边可能会非常深;也就是说树的一条分支会有很多层,而其它却有几层,如下图所示 这会在需要的某条边上添加、移除和搜索某个节点时引起一些性能问题。为了解决这个问题,我们需要去平衡它的高度。 8.4.1 自平衡树-AVL树AVL树是一种自平衡树。添加或移除节点时,AVL树会尝试保持自平衡,任意一个节点(不论深度)的左子树和右子树高度最多相差1.添加或移除节点时,AVL树会尽可能尝试转换为完全树。 我们开始创建AVLTree类: 123456export default class AVLTree extends BinarySearchTree { constructor() { super(); this.root = null; ...
考研-数据结构复习
3.2 队列3.2.1 队列的基本概念1队列的定义队列(Queue)简称队,也是一种操作受限的线性表,只允许在表的一端进行插入,而在表的另一端删除。向队列中插入元素称为入队或进队;删除元素称为出队或离队。这和我们日常生活中的排队是一致的,最早排队的也是最早离队的,其操作的特性是先进先出(First In First Out,FIFO),如下图所示 队头(Front)。允许删除的一端,又称队首。队尾(Rear)。允许插入的一队。
JavaScript 二叉树
树树是一种分层的抽象模型。现实生活中最常见的树的例子就是家谱,或是公司的组织架构图,如下图所示: 树的相关术语一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点(除了顶层的第一个节点)以及零个或多个子节点。位于树顶部的节点叫作根节点。它没有父节点。树种的每个元素叫做节点,节点分为内部节点和外部节点。至少有一个子节点的节点称为内部节点。没有子元素的节点称为外部节点或叶节点一个节点可以有祖先和后代,一个节点(除了根节点)的祖先包括父节点、祖父节点等。一个节点的后代包括子节点、孙节点等有关树的另一个术语是子树。子树由节点和它的后代构成。节点的一个属性是深度,节点的深度取决于它的祖先节点数量。树的高度取决于所有节点深度的最大值。 二叉树和二叉搜索树二叉树种的节点最多只能有两个子节点:一个是左侧子节点。另一个是右侧子节点。这个定义有助于我们写出更搞笑地在树种插入、查找、删除节点的算法。二叉搜索树(BST)是二叉树的一种,但是只允许你在左侧节点存储(比父节点)小的值,在右侧节点存储(比父节点)大的值。 8.1.1...
windows系统PhpStorm无限试用30天的方法
JetBrains家的软件都是可以免费试用30天的,通过了解发现,他会在电脑本地上生成一些密钥和试用信息文件。 所以我们可以大胆的尝试,将它们删除掉,就可以实现无限试用,亲测可用!话不多说,教程开始: 1.确保软件处于关闭状态 2.删除掉本地文件 12删除目录 C:\Users\用户名\AppData\Roaming\JetBrains\PhpStorm2020.1\eval删除文件 C:\Users\用户名\AppData\Roaming\JetBrains\PhpStorm2020.1\options\other.xml 3.删除掉注册表项(打开注册表编辑器regedit) 12删除注册表项:HKEY_CURRENT_USER\Software\JavaSoft\Prefs\jetbrains\phpstorm 4.启动PhpStorm软件,选择30天试用,继续奔放~
JavaScript 字典和散列表
7.1 字典 我们知道,集合表示一组互不相同的元素(不能重复的元素)。在字典中,存储的是[键, 值]对,其中键名是用来查询特定元素的。字典和集合很相似,集合以[值, 值]的形式存储元素,字典则是以[键, 值]的形式来存储元素。字典也称作映射、符号表或关联数组 7.1.1 创建字典类以下就是我们Dictionary类的骨架: 12345678910111213141516function defaultToString(key) { if(key === null){ return 'NULL' }else if (key === undefined){ return 'UNDEFINED'; }else if(typeof key === 'string' || key instanceof String){ return `${key}`; } ...
MySql高频面试题
1、MySql索引使用有哪些注意事项呢?我们可以用两个方面来回答这个问题: 索引哪些情况会失效 查询条件包含 or,会导致索引失效。 隐式类型转换,会导致索引失效,例如 age 字段类型是 int,我们 where age = “1”,这样就会触发隐式类型转换。 like 通配符会导致索引失效,注意:”ABC%” 不会失效,会走 range 索引,”% ABC” 索引会失效 联合索引,查询时的条件列不是联合索引中的第一个列,索引失效。 对索引字段进行函数运算。 对索引列运算(如,+、-、*、/),索引失效。 索引字段上使用(!= 或者 < >,not in)时,会导致索引失效。 索引字段上使用 is null, is not null,可能导致索引失效。 相 join 的两个表的字符编码不同,不能命中索引,会导致笛卡尔积的循环计算 mysql 估计使用全表扫描要比使用索引快,则不使用索引。 索引不适合哪种场景? 数据量少的不适合加索引 更新比较频繁的也不适合加索引 离散性低的字段不适合加索引(如性别) 2、 MySQL...
JavaScript 集合
6 集合 集合是由一组无序且唯一(即不能重复)的项组成。该数据结构使用了与有限集合相同的数学概念,但应用在计算机科学的数据结构中。 6.1 创建Set类用下面的Set类以及它的构造函数声明作为开始 12345class Set { constructor() { this.items = {}; }} 接下来我们需要声明一些集合可用的方法: add(element):向集合添加一个新的项delete(element):从集合里移除一个值has(element):如果值在集合中,返回true,否则返回falseclear():移除集合中的所有项size():返回集合所包含元素的数量,与数组的length属性类似values():返回一个包含集合中所有值的数组 6.1.1 has(element)方法由于has(element)方法会被add、delete等其它方法调用。它用来检验某个元素是否存在于集合中。所以我们先来实现它: 123has(element){ return...
JavaScript 链表
链表 链表用来存储有序的元素集合,与数组不同,链表中的元素并非保存在连续的存储空间内,每个元素由一个存储元素本身的节点和一个指向下一个元素的指针构成。当要移动或删除元素时,只需要修改相应元素上的指针就可以了。对链表元素的操作要比对数组元素的操作效率更高 5.1 单项链表下面是单项链表的数据结构展示图: 要表示链表中的元素,我们需要一个助手类,叫作Node。表示我们想要添加到链表中的项,它包含一个element属性,该属性表示要加入链表元素的值,和一个next属性,该属性是指向链表中下一个元素的指针。它的代码如下: 1234567class Node { constructor(element) { this.element = element; this.next = null; }} 然后我们需要创建主类,叫LinkedList类,我们来规划一下这个类可用到的方法以及方法的作用。 **push(element)**: 向链表尾部添加节点 **insert(position,...
JavaScript 队列
队列是遵循先进先出(FIFO,也称先来先服务)原则的一组有序的项。队列在尾部添加新元素,并从顶部移除元素。最新添加的元素必须排在队列的末尾。 在现实中,最常见的队列的例子就是排队。在电影院,学校饭堂,我们都会排队。排在第一位的人会先接受服务。 4.1...