大家好,最近更新的稍微慢了许多,参加了一些公司和外界的技术培训,也跟一些小伙伴聊了些技术文章,总的来说很不理想,讲的内容高大上,落地的过程踩坑很严重,和没听的效果差不多,感觉这几年,圈子太浮躁了,对新技术趋之若鹜,恨不得昨天出来,今天就用到项目上。很值得我反思了。
技术在变,年龄在变,但唯一不变的还是我们的核心技术:Linux、C、TCP\IP这些,不管上层建筑如何变化,都只是在底层基础上封装。 建议大家有选择的去找学习资源,不要当了韭菜,去知识的源头学习,不要尝人家消化过的知识。
在前面的文章中,我们介绍了 Collection 篇 和一篇 HashMap,我们接下来介绍 剩下的 Map 实现,今天我们先来介绍排序二叉树和红黑树,为接下来的 TreeMap 和 TreeSet 做准备,顺便带大家重温一波数据结构。废话不多说,我们正文开始。
二叉查找树(英语:Binary Search Tree),也称为二叉搜索树、有序二叉树(ordered binary tree)或排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:
如图,2棵树都是排序二叉树。
下面是一个 树的结构:
class Node {
/**
* 节点
*/
Object data;
/**
* 父节点
*/
Node parent;
/**
* 左子节点
*/
Node left;
/**
* 右子节点
*/
Node right;
public Node(Object data, Node parent, Node left, Node right) {
this.data = data;
this.parent = parent;
this.left = left;
this.right = right;
}
}
排序二叉树有个很好的查找算法,在查找某个元素时,比较高效,当然和数组的下标定位不能比,那是硬件支持的。
private Node getNode(Object e) {
Node parent = root;
while (parent != null) {
//比较父节点元素 和传入的元素
int compareValue = e.compareTo(parent.data);
if(compareValue < 0){
//查找左子树
parent = parent.left;
}
else if(compareValue > 0){
//查找右子树
parent = parent.right;
}
else{
return parent;
}
}
return null;
}
向排序二叉树中插入某个元素节点 data 的过程如下:
private void insertNode(Object o) {
if (root == null) {
root = new Node(o, null,null,null);
}
Node current = root;
Node parent = current;
int compareValue = 0;
while (current != null) {
compareValue = o.compareTo(parent.data);
// 新节点的值 > parent的值
if(compareValue > 0){
//查找右子树
current = current.right;
}else if(compareValue < 0){
//查找左子树
current = current.left;
} else {
return;
}
}
//创建新节点
Node newNode = new Node(o, parent, null, null);
//新节点的值大于 父节点值
if(compareValue > 0){
//设置为右子节点
parent.right = newNode;
}else{
//设置为左子节点
parent.left = newNode;
}
}
排序二叉树的删除要稍 微复杂一些:
Node parent = node.parent;
//要删除的当前节点没有子节点
if (node.left == null && node.right == null) {
if (o.compareTo(parent.data)) {
parent.right = null;
} else {
parent.left = null;
}
}
比如 我们删除 0001
//要删除的元素只有一个子节点
//只有一个左节点
if (node.left != null && node.right == null) {
//被删除的节点是父节点的左节点
if (node == parent.left) {
//父节点的左子节点就是当前节点的左子节点
parent.left = node.left;
}
node.left.parent = parent;
}
// 只有一个右节点
else if (node.left == null && node.right != null) {
if (node == parent.right) {
parent.right = node.right;
}
node.right.parent = node.right;
}
上面我们讲的都是高度平衡的排序二叉树:
平衡定义:任何节点的左右子树的高度差最多为一。
但是也有一种极端情况,二叉树直接退化成链表了。比如:
就算没有退化成链表,排序二叉树如果高度不平衡的情况下,效率也会低。
而平衡的排序二叉树又被大家成为 AVL 树,根据它的作者 G.M.Adelson-Velsky 、E.M.Landis 的名字命名的。AVL 算法在插入和删除节点时,会根据一次或者是多次旋转来重新平衡树。当然我们这篇的例子没有写重要的保持平衡算法,只是给大家先回忆一下。之后会在专门的数据结构篇给大家讲解。
我们下篇讲的 TreeMap 就是使用的红黑树。红黑树(Red–black tree)与 AVL 树类似,是一种自平衡的二叉查找树,插入和删除节点是通过选择操作来平衡的,不过它不是高度平衡的,而是大致平衡。比如
红黑树有如下性质:
红黑树确保任意一条从跟到叶子节点的路径,没有任何一条的长度比其他路径长过两倍。
比如,最短路径 3 -> 1 的是 2
最长路径3 -> 9 -> 15 ->16 的是4 。正好是2倍。
我们这里只说下红黑树的核心-旋转操作
还是如图
这时,我们插入 20
上面我们提到了树的旋转。我们下面再提下相关概念
例子:
例子: