一、数据结构

布满荆棘的人生 2022-11-03 10:51 15阅读 0赞

# 1.数组 #

char[] cs = new char[]{'a','b','c','d'};
    char[] cs1 = new char[4];
    cs1[0] = 'a';

注意：注意数组下标越界

char[] cs = new char[]{'a','b','c','d'};
    System.out.println(cs[4]);

特点：  
1.内存地址连续，使用之前必须指定数组长度  
2.可以通过下标访问的方式访问成员，查询效率高  
3.增删操作会给系统带来性能消耗--因为只能把需要保留的数据拷贝到一个新数组

# 2.数据链表 #

单向链表、双向链表

双向链表

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1Y2lmZXJsb25neHU_size_16_color_FFFFFF_t_70][]

特点：  
1.灵活的空间要求，存储空间不要求连续  
2.不支持下标访问，支持顺序遍历检索  
3.针对增删操作，效率更高，只和操作节点的前后节点有关系，无需移动元素  
4.针对查询操作，效率没有数组高

LinkedList：通过双向链表结构实现

private static class Node<E> {
            E item; //节点元素
            Node<E> next; //下一个节点
            Node<E> prev; //上一个节点
    
            Node(Node<E> prev, E element, Node<E> next) {
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
        }

# 3.树 #

二叉树性能介于数组和链表之间。  
添加元素时和当前节点值对比，如果比当前节点大，添加在节点下右侧，如果比当前节点小，添加到节点下左侧。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1Y2lmZXJsb25neHU_size_16_color_FFFFFF_t_70 1][]

二叉树特点：  
1.某节点的左子树节点值仅包含小于该节点值  
2.某节点的右子树节点值仅包含大于该节点值  
3.左右子树每个也必须是二叉找树  
4.顺序排列

不平衡二叉树特点：  
1.查询效率不高

面对这个问题，就要想办法让不平衡变得平衡，红黑树就是去除不平衡二叉树的解决方案，从而达到树的平衡。

红黑树Red-Black Tree\[RBT\]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1Y2lmZXJsb25neHU_size_16_color_FFFFFF_t_70 2][]

RBT是一个**自平衡**【不是绝对的平衡】的二叉查找树，树上的节点满足如下规则：  
1.每个节点要么红色，要么黑色  
2.根节点必须是黑色  
3.每个叶子节点【空节点】是黑色  
4.每个红色节点的子节点必须是黑色  
5.任意节点到每个叶子节点的路径包含相同数量的黑节点

如何实现以上规则：  
1.recolor 重新标记节点颜色为红/黑色  
2.rotation 旋转节点实现平衡

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1Y2lmZXJsb25neHU_size_16_color_FFFFFF_t_70]: /images/20221024/a03dc2f9f709421aa9505fd1b7ce89ad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1Y2lmZXJsb25neHU_size_16_color_FFFFFF_t_70 1]: /images/20221024/1c9bbf258b2e4b52b0bce8e358fb7b09.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1Y2lmZXJsb25neHU_size_16_color_FFFFFF_t_70 2]: /images/20221024/2c2d16deebd04ec28456d43a905dbf80.png