java21

1.数据结构之二叉树，二叉查找树，平衡二叉树

 

原理：和节点比较大小然后选左边还是右边

注意：中序遍历最常见，因为遍历的结果是从小到大

注意是任意节点，上面的二叉查找树的节点10的左子树高度是0，右子树高度是3，所以不是平衡二叉树。

演变都是为了提高查询和遍历效率

节点12就是添加的节点，节点10就是第一个不平衡的节点即支点

2.数据结构之红黑树（自平衡二叉查找树）

叶节点不算子节点，节点1没有左子节点，其左子节点指针为nil;节点11没有子节点,其左右子节点指针都是nil

平衡二叉树的弊端：添加节点时需要频繁旋转

可以看出节点都是想要尽可能得红，只是不能而已,即：

红黑树的添加节点很难

3.set集合

扩容时机：

当长度为16的数组存储了12个元素时会扩容成原来的2倍

链表转化为红黑树的时机：

会报错，因为没重写排序规则

所以TreeSet不需要重写hashCode和equals方法