理想情况下,通过 BST 查找节点,所需要检查的节点数可以减半。
平衡二叉树:当且仅当任何节点的两棵子树的高度差不大于 1 的二叉树。由前苏联的数学家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉树,根据科学家的英文名也称为 AVL 树。
平衡二叉树本质上也是一颗二叉查找树,不过为了限制左右子树的高度差,避免出现倾斜树等偏向于线性结构演化的情况,所以对二叉搜索树中每个节点的左右子树作了限制,左右子树的高度差称之为平衡因子,树中每个节点的平衡因子绝对值不大于 1。
平衡二叉树的难点在于,当删除或者增加节点的情况下,如何通过左旋或者右旋的方式来保持左右平衡。
Java 中最常见的平衡二叉树就是红黑树,节点是红色或者黑色,通过颜色的约束来维持着二叉树的平衡:
1)每个节点都只能是红色或者黑色
2)根节点是黑色
3)每个叶节点(NIL 节点,空节点)是黑色的。
4)如果一个节点是红色的,则它两个子节点都是黑色的。也就是说在一条路径上不能出现相邻的两个红色节点。
5)从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
B 树:一种对读写操作进行优化的自平衡的二叉查找树,能够保持数据有序,拥有多于两个的子树。数据库的索引技术里就用到了 B 树。
⑥、堆
堆可以被看做是一棵树的数组对象,具有以下特点:
堆中某个节点的值总是不大于或不小于其父节点的值;
堆总是一棵完全二叉树。
将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。
⑦、图
图是一种复杂的非线性结构,由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G 表示一个图,V 是图 G 中顶点的集合,E 是图 G 中边的集合。
上图共有 V0,V1,V2,V3 这 4 个顶点,4 个顶点之间共有 5 条边。
在线性结构中,数据元素之间满足唯一的线性关系,每个数据元素(除第一个和最后一个外)均有唯一的“前驱”和“后继”;
在树形结构中,数据元素之间有着明显的层次关系,并且每个数据元素只与上一层中的一个元素(父节点)及下一层的多个元素(子节点)相关;
而在图形结构中,节点之间的关系是任意的,图中任意两个数据元素之间都有可能相关。
⑧、哈希表
哈希表(Hash Table),也叫散列表,是一种可以通过关键码值(key-value)直接访问的数据结构,它最大的特点就是可以快速实现查找、插入和删除。
数组的最大特点就是查找容易,插入和删除困难;而链表正好相反,查找困难,而插入和删除容易。哈希表很完美地结合了两者的优点, Java 的 HashMap 在此基础上还加入了树的优点。
哈希函数在哈希表中起着⾮常关键的作⽤,它可以把任意长度的输入变换成固定长度的输出,该输出就是哈希值。哈希函数使得一个数据序列的访问过程变得更加迅速有效,通过哈希函数,数据元素能够被很快的进行定位。
若关键字为 k,则其值存放在 hash(k) 的存储位置上。由此,不需要遍历就可以直接取得 k 对应的值。
对于任意两个不同的数据块,其哈希值相同的可能性极小,也就是说,对于一个给定的数据块,找到和它哈希值相同的数据块极为困难。再者,对于一个数据块,哪怕只改动它的一个比特位,其哈希值的改动也会非常的大——这正是 Hash 存在的价值!
尽管可能性极小,但仍然会发生,如果哈希冲突了,Java 的 HashMap 会在数组的同一个位置上增加链表,如果链表的长度大于 8,将会转化成红黑树进行处理——这就是所谓的拉链法(数组+链表)。
说句实在话,照这个进度恶补下去,我感觉要秃的节奏,不过,如果能够变得更强,值了——对,值了。还有一些小伙伴要我推荐一些算法和数据结构方面的书籍,我在 GitHub 上搜罗了一些比较受欢迎的,点击链接就可以下载,希望我的用心可以帮助到你。
链接:https://pan.baidu.com/s/1rB-CCjjpKPidOio7Ov_0YA 密码:g5pl
大爷的,我自己原创的 PDF 都被投诉,黑子真可怕。如链接失效,请转至备用链接:https://shimo.im/docs/pJQv6qVcHqdYwrxx