前言 红黑树警告! 虽说很多人都会把红黑树当作面经交流时的一个玩笑话,但是红黑树作为一个比较重要的点,还是有可能在面试时被提到的。JDK 1.8 后,HashMap 中,如果一条链表的长度大于 8,且哈希桶的个数大于等于 64 时,这条链表就会转化为红黑树。 红黑树在面试时一般会考察其基本的特性,进阶一点会考察左旋右旋的方式,极致的考察就会让面试者写出在红黑树中插入/删除节点的代码。 二叉查找树 我们首先从二叉查找树(Binary Search Tree,BST)开始。一棵红黑树,首先是一棵二叉查找树。 一棵二叉查找树具备以下特征: 左子树上所有节点的值均小于或等于它的根节点的值 右子树上所...