2021-11-05 java集合

2021-11-05 java集合

初步认识java集合

• • 数组
  • 链表
  • 平衡二叉树
  • 不平衡二叉树
  • 红黑树
  • 红黑树平衡方法

数组

特点：
A.内存地址连续，
B.可以通过下标的成员访问,下标访问的性能高
C.增删 *** 作带来更大的性能消耗(保证数据越界的问题,需动态扩容)

链表

特点：
A.灵活的空间要求,存储空间不要求连续
B.不支持下标的访问.支持顺序的遍历搜索
C.针对增删 *** 作找到对应的节点改变链表的头尾指向即可,无需移动元素存储位置

平衡二叉树

二叉树具有如下的特点
(1)某节点的左子树节点值仅包含小于该节点值
(2)某节点的右子树节点值仅包含大于该节点值
(3)左右子树每个也必须是二叉查找树
(4)顺序排列

不平衡二叉树

   查询效率不高，解决办法去除顶端，让侧边慢慢强壮和平衡，红黑树其实就是去除二叉树顶端优势的解决方案

红黑树

红黑树是一个自平衡【不是绝对平衡】的二叉查找树

红黑树节点的规则

性质1：每个节点要么是黑色，要么是红色。
性质2：根节点是黑色。
性质3：每个叶子节点（NIL）是黑色。
性质4：每个红色结点的两个子结点一定都是黑色。
性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点
红黑树练习网站：http://algoanim.ide.sk/index.php?page=showanim&id=63

红黑树平衡方法

三种 *** 作：左旋，右旋，变色

左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，
      右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。
      
右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，
左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。

变色：结点的颜色由红变黑或由黑变红。