Java笔记——数据结构

Master

April 21, 2021

681 views

One comment

1135 words

笔记类

### 1.数组

```java
Char[] cs = new Char[]{'J','U','P','I','T','E','R'};
Char[] cs1 = new Char[7];
cs1[0] = 'J';
....
```

特点：

1.内存地址连续，使用之前必须要指定数组长度
2.可以通过下标访问的方式访问成员，查询效率高
3.增删操作会给系统带来性能消耗（存在数据下标越界的问题，需要动态扩容）

### 2.链表

单向链表和双向链表

双向链表

特点

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

LinkedList

```java
    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.树

#### 红黑树

红黑树,Red-Black Tree [RBT] 是一个<b>自平衡</b>（不是绝对）的二叉查找树,树上的节点满足如下的规则

1.每个节点要么是红色，要么是黑色。
2.根节点必须是黑色
3.每个叶子节点是黑色
4.每个红色节点的两个子节点必须是黑色
5.任意节点到每个叶子节点的路径包含相同数量的黑节点

#### 黑平衡二叉树

1.recolor  重新标志节点为红色或者黑色
2.rotation 旋转  树达到平衡的关键

红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色

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

#### 红黑树插入的场景

1.红黑树为空
2.父节点为黑色节点

Last modification：November 17, 2021

欢迎留下您的脚印

Java笔记——数据结构

Master • 2021 年 04 月 21 日

One comment

Leave a Comment Cancel reply 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

Java笔记——数据结构

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款