复杂度
什么是算法
算法是用于解决特定问题一系列执行步骤
如果单从执行效率上进行评估，可能会想到这么一种方案比较不同算法对同一组输入的执行处理时间，这种叫事后统计法
评估算法优劣
时间复杂度：程序指令执行次数
空间复杂度：估算所需占用的存储空间
大O表示法
表示数据规模n对应的复杂度
9 >> O(1)
2n+3 >> O(n^2)
n^2^
9 >> O(1)
2n+3 >> O(n2)
n2 +2n +6 >> O(n2)
n3 +2n +6 >> O(n3)
对数阶的细节
所以 log2n 、log9n 统称为 logn
log2n = log29 ∗ log9n
算法优化方向
尽量少的存储空间
尽量少的执行步骤
空间换时间
时间换空间
多个数据规模
public static void test(int n, int k ){
for (int i = 0; i < n; i++) {
System.out.println("test");
}
for (int i = 0; i < k; i++) {
System.out.println("test");
}
}
补充
一般O（n）计算方法：
用常数1取代运行时间中所有加法常数。
在修改后的运行次数函数中，只保留最高阶项。
如果最高阶项系数存在且不是1，则去除与这个项相乘的常数。
空间复杂度：函数中创建对象的个数关于问题规模函数表达式，一般情况下也用O渐进表示法表示。
递归算法的空间复杂度：递归的深度*递归创建空间的大小。
什么是数据结构
数据结构使计算机存储，组织数据的方式
线性结构：行星表，数组链表栈队列，哈希表
树形结构：AVL树，红黑树，B树，堆，Trie，哈夫曼树，并查集
图形结构：邻接矩阵，邻接表
数组
数组是一种顺序存储线性表，所有元素内存地址是连续的
int [] array = new int[] {11,22,33}
动态数组接口设计
◼ int size(); // 元素的数量
◼ boolean isEmpty(); // 是否为空
◼ boolean contains(E element); // 是否包含某个元素
◼ void add(E element); // 添加元素到最后面
◼ E get(int index); // 返回index位置对应的元素
◼ E set(int index, E element); // 设置index位置的元素
◼ void add(int index, E element); // 往index位置添加元素
◼ E remove(int index); // 删除index位置对应的元素
◼ int indexOf(E element); // 查看元素的位置
◼ void clear(); // 清除所有元素
动态数组设计
成员变量会自动初始化
int 类型自动初始化 0
对象初始化null
添加元素add
打印数组
重写toString
在toString 方法中将元素拼接成字符串
字符串拼接建议使用StringBuilder
删除元素
添加元素
数组扩容
import java.util.Arrays;
public class CopyArrayDemo {
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 4, 5 };
// 数组扩容（一）
// int[] arr = {1,2,3,4,5}; //数组arr的下标分别为：0 1 2 3 4
int[] arr_new = new int[6]; // 数组arr_new的下标分别为：0 1 2 3 4 5
for (int i = 0; i < arr.length; i++) { //遍历一遍，将数组arr的值传入数组arr_new中
arr_new[i] = arr[i];
}
// 为新数组赋值
arr_new[arr_new.length - 1] = 6;
for (int a : arr_new) {
System.out.print(a + " ");
}
System.out.println(); //换行
// 数组扩容（二）
// 第一个参数是拷贝的数组，第二个参数扩容长度，并且返回一个新的数组
int[] copyOf = Arrays.copyOf(arr, arr.length * 2);
for (int a : copyOf) {
System.out.print(a + " ");
}
System.out.println(); //换行
// 数组扩容（三）
int arr2[] = { 10, 20, 30, 40, 50, 60, 70, 80, 90 };
/*
* src：表示复制的源数组
* srcPos：代表从源数组哪一个元素开始复制（下标）
* dest：目标数组
* destPos：从目标数组的哪一个元素开始粘贴源数组的数据
* length：复制源数组的长度是多少
*/
System.arraycopy(arr, 1, arr2, 3, arr.length - 1);
for (int a : arr2) {
System.out.print(a + " ");
}
}
}
泛型
使用泛型技术让动态数组更加通用，可以存放任何数据类型
public class ArrayList<E>{
private int size;
private E[] elements;
}
elements = (E[]) new Object[capcity];
ArrayList<Interger> list = new ArrayList<>();
对象数组
链表
动态数组有个明显的缺点
可能会造成内存空间大量浪费
链表可以办到用多少就申请多少内存
链表是一个链式存储线性表，所有元素内存地址不一定连续
接口设计
清空元素
添加元素
node方法用于获取index位置节点
private Node<E> node(int index){
rangeCheck(index)
Node<E>node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node
}
添加元素
public void add(int index,E element){
rangeCheck(index)
if(index==0){
first = new Node<element,first>;
}else{
Node<E>prev = node(index-1);
prev.next = new Node<>(element,prev.next)
}
}
删除元素
反转一个列表
队列底层也可以使用动态数组实现，并且各项接口也可以优化到O(1)的时间复杂度，这个用数组实现并且优化之后的队列叫，循环队列
向下取整：只取前面的整数
4.1 4
4
向上取整：如果小数不为0，前面的整数加1，小数为0，只取整数
4.5 5
4.0 4
数组随机访问
随机访问速度快
elements[n]的效率与n是多少无关
动态数组链表复杂度分析
add
最好 O(1)
最坏O(n)
平均O(1)
均摊O(1)
问：什么情况下适合使用均摊复杂度
经过连续多次复杂度比较低的情况后，出现个别复杂度比较高
动态数组缩容
如果内存比较紧张，动态数组比较多的剩余空间可以考虑进行缩容操作
如果扩容倍数，缩容时机设计不当，有可能导致复杂度振荡
双向链表
使用双向链表可以提升链表综合性能
双向链表node法
双向链表add
remove
双向链表 vs 动态数组
◼ 动态数组：开辟、销毁内存空间的次数相对较少，但可能造成内存空间浪费（可以通过缩容解决）
◼ 双向链表：开辟、销毁内存空间的次数相对较多，但不会造成内存空间的浪费
◼ 如果频繁在尾部进行添加、删除操作，动态数组、双向链表均可选择
◼ 如果频繁在头部进行添加、删除操作，建议选择使用双向链表
◼ 如果有频繁的（在任意位置）添加、删除操作，建议选择使用双向链表
◼ 如果有频繁的查询操作（随机访问操作），建议选择使用动态数组
◼ 有了双向链表，单向链表是否就没有任何用处了？
并非如此，在哈希表的设计中就用到了单链表
至于原因，在哈希表章节中会讲到
单向循环列表
单向add
单向remove
双向循环列表
如何发挥循环列表最大威力
可以考虑1个成员变量，3个方法
current ：用于指向某个节点
void reset() 让current 指向头节点 first
E next 让 current 往后走一步，也就是 current = current.next
E remove() ：删除 current 指向的节点，删除成功后让 current 指向下一个节点
静态列表
前面所学习的链表，是依赖于指针（引用）实现的
◼ 有些编程语言是没有指针的，比如早期的 BASIC、FORTRAN 语言
◼ 没有指针的情况下，如何实现链表？
可以通过数组来模拟链表，称为静态链表
数组的每个元素存放 2 个数据：值、下个元素的索引
数组 0 位置存放的是头结点信息
思考：如果数组的每个元素只能存放 1 个数据呢？
那就使用 2 个数组，1 个数组存放索引关系，1 个数组存放值
栈
栈是一种特殊的线性表，只能在一端进行操作
往栈中添加元素操作，push 入栈
从栈中移除元素操作
pop 出栈，移除栈顶元素
后进先出
栈接口
int size() 元素数量
boolean isEmpty()是否是空
void push(E element)入栈
E top();获取栈顶元素
void clear() 清空
栈 括号面试题
判断括号的有效性可以使用「栈」这一数据结构来解决。
我们遍历给定的字符串 s。当我们遇到一个左括号时，我们会期望在后续的遍历中，有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合，因此我们可以将这个左括号放入栈顶。
当我们遇到一个右括号时，我们需要将一个相同类型的左括号闭合。此时，我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，那么字符串 s 无效，返回 False。为了快速判断括号的类型，我们可以使用哈希表存储每一种括号。哈希表的键为右括号，值为相同类型的左括号。
在遍历结束后，如果栈中没有左括号，说明我们将字符串 s 中的所有左括号闭合，返回 True，否则返回 False。
注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回 /text{False}False，省去后续的遍历判断过程。
class Solution {
public boolean isValid(String s) {
int n = s.length();
if (n % 2 == 1) {
return false;
}
Map<Character, Character> pairs = new HashMap<Character, Character>() {{
put(')', '(');
put(']', '[');
put('}', '{');
}};
Deque<Character> stack = new LinkedList<Character>();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (pairs.containsKey(ch)) {
if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
return false;
}
stack.pop();
} else {
stack.push(ch);
}
}
return stack.isEmpty();
}
}
时间复杂度：O(n)O(n)，其中 nn 是字符串 ss 的长度。
空间复杂度：O(n+∣Σ∣)，其中 Σ 表示字符集，本题中字符串只包含 66 种括号，∣Σ∣=6。栈中的字符数量为 O(n)，而哈希表使用的空间为 O((∣Σ∣)，相加即可得到总空间复杂度。
有效的括号
遇见左字符，将左字符入栈
如果栈是空的，说明括号无效
如果栈不是空的将栈顶字符出栈，和右字符匹配
如果左右字符不配，说明括号无效
如果左右字符匹配，继续扫描下一个字符
所有字符扫描完毕后
栈是空，说明括号有效
栈不是空，说明括号无效
队列
队列是特殊线性表，只能在头尾两端进行操作
队尾(rear) :只能从队尾添加元素，一般叫 enQueue 入队
对头(front) 只能从队头移除元素，一般叫 deQueue 出队
先进先出原则
队列接口设计
int size() 元素数量
boolean isEmpty()
void clear()
void enQueue (E element)
E deQueue() 出队
E front() 获取队列头元素
动态数组、链表
优先使用双向链表，因为队列主要是往头尾操作元素
用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
private int front;
public void push(int x) {
if (s1.empty())
front = x;
while (!s1.isEmpty())
s2.push(s1.pop());
s2.push(x);
while (!s2.isEmpty())
s1.push(s2.pop());
}
复杂度分析
时间复杂度：O(n)O(n)
对于除了新元素之外的所有元素，它们都会被压入两次，弹出两次。新元素只被压入一次，弹出一次。这个过程产生了 4n + 24n+2 次操作，其中 nn 是队列的大小。由于 压入 操作和 弹出 操作的时间复杂度为 O(1)O(1)， 所以时间复杂度为 O(n)O(n)。
空间复杂度：O(n)O(n)
需要额外的内存来存储队列中的元素。
双端队列
双端队列是在头尾两端添加，删除队列
int size()
boolean isEmpty()
◼ void clear(); // 清空
◼ void enQueueRear(E element); // 从队尾入队
◼ E deQueueFront(); // 从队头出队
◼ void enQueueFront(E element); // 从队头入队
◼ E deQueueRear(); // 从队尾出队
◼ E front(); // 获取队列的头元素
◼ E rear(); // 获取队列的尾元素
循环队列底层使用动态数组实现，并且各项接口也可以优化到O(1)
时间复杂度
◼ 这个用数组实现并且优化之后的队列也叫做：循环队列
循环队列
循环双端队列
%运算符优化
尽量避免使用乘*、除/、模%、浮点数运算，效率低下
二叉树
节点根节点，父节点，子节点，兄弟节点
节点的度：子树的个数
树的度:所有节点度中最大值
叶子节点：度是0节点
非叶子节点：度不为0的节点
层数：根节点在1层，根节点子节点在2层
节点深度：从根节点到当前节点唯一路径上节点总数
节点的高度：从当前节点到最远叶子节点路径上节点总数
树的深度：所有节点深度最大值
树的高度：所有节点高度最大值
树的深度等于树的高度
有序树，无序树，森林
有序树
树中任意节点的子节点之间有顺序关系
无序树
树中任意节点的子节点之间没有顺序关系
也称为“自由树
森林
由 m（m ≥ 0）棵互不相交的树组成的集合
二叉树特点
每个节点度最大是2
左子树和右子树有顺序
即使是某节点只有一个子树，也要区分左右子树
非空二叉树的第 i 层，最多有 2i-1 个节点（ i ≥ 1 ）
在高度为 h 的二叉树上最多有 2h-1个结点（ h ≥ 1 ）
对于任何一棵非空二叉树，如果叶子节点个数为 n0，度为 2 的节点个数为 n2，则有: n0 = n2 + 1 假设度为 1 的节点个数为 n1，那么二叉树的节点总数 n = n0 + n1 + n2
二叉树的边数 T = n1 + 2 * n2 = n – 1 = n0 + n1 + n2 – 1
因此 n0 = n2 + 1
真二叉树
所有节点度都要么是0，要么是2
满二叉树
满二叉树：所有节点的度都要么为 0，要么为 2。且所有的叶子节点都在最后一层
假设满二叉树的高度为 h（ h ≥ 1 ），那么 第 i 层的节点数量 2i-1
叶子节点数量2h-1
✓n = 2 h − 1 = 2 0 + 2 1 + 2 2 + ⋯ + 2 h−1
h = log2(n + 1)
完全二叉树
叶子节点只会出现最后2层，最后1层叶子节点都靠左对齐
完全二叉树从根节点到倒数第二层是一个满二叉树
满二叉树一定时完全二叉树，完全二叉树不一定是满二叉树
性质
度为1的节点只有左子树
度是1的节点要么是1个要么是0个
同样是节点数量的二叉树，完全二叉树高度最小
一棵有 n 个节点的完全二叉树（n > 0），从上到下、从左到右对节点从 1 开始进行编号，对任意第 i 个节点
如果 i = 1 ，它是根节点
如果 i > 1 ，它的父节点编号为 floor( i / 2 )
如果 2i ≤ n ，它的左子节点编号为 2i
如果 2i > n ，它无左子节点
如果 2i + 1 ≤ n ，它的右子节点编号为 2i + 1
如果 2i + 1 > n ，它无右子节点
一棵有 n 个节点的完全二叉树（n > 0），从上到下、从左到右对节点从 0 开始进行编号，对任意第 i 个节点
如果 i = 0 ，它是根节点
如果 i > 0 ，它的父节点编号为 floor( (i – 1) / 2 )
如果 2i + 1 ≤ n – 1 ，它的左子节点编号为 2i + 1
如果 2i + 1 > n – 1 ，它无左子节点
如果 2i + 2 ≤ n – 1 ，它的右子节点编号为 2i + 2
如果 2i + 2 > n – 1 ，它无右子节点
◼ 如果一棵完全二叉树有 768 个节点，求叶子节点的个数
假设叶子节点个数为 n0，度为 1 的节点个数为 n1，度为 2 的节点个数为 n2
总结点个数 n = n0 + n1 + n2，而且 n0 = n2 + 1
✓ n = 2n0 + n1 – 1
完全二叉树的 n1 要么为 0，要么为 1
✓ n1为1时，n = 2n0，n 必然是偶数
➢ 叶子节点个数 n0 = n / 2，非叶子节点个数 n1 + n2 = n / 2
✓ n1为0时，n = 2n0 – 1，n 必然是奇数
➢ 叶子节点个数 n0 = (n + 1) / 2，非叶子节点个数 n1 + n2 = (n – 1) / 2
叶子节点个数 n0 = floor( (n + 1) / 2 ) = ceiling( n / 2 )
非叶子节点个数 n1 + n2 = floor( n / 2 ) = ceiling( (n – 1) / 2 )
因此叶子节点个数为 384
二叉树遍历
把所有元素都访问一遍
线性数据结构遍历比较简单
正序遍历
逆序遍历
前序
中序
后序
层序
前序遍历
先访问根节点，前序遍历左子树，前序遍历右子树
中序遍历
左子树 ，根节点，右子树
后序遍历
左子树，右子树，根节点
层序遍历
从上到下，从左到右依次遍历
◼ 实现思路：使用队列
1. 将根节点入队
2. 循环执行以下操作，直到队列为空
将队头节点 A 出队，进行访问
将 A 的左子节点入队
将 A 的右子节点入队
/**
* 前序遍历
*/
public void preorderTraversal() {
preorderTraversal(root);
}
private void preorderTraversal(Node<E> node) {
if (node == null) return;
System.out.println(node.element);
preorderTraversal(node.left);
preorderTraversal(node.right);
}
/**
* 中序遍历
*/
public void inorderTraversal() {
inorderTraversal(root);
}
private void inorderTraversal(Node<E> node) {
if (node == null) return;
inorderTraversal(node.left);
System.out.println(node.element);
inorderTraversal(node.right);
}
/**
* 后序遍历
*/
public void postorderTraversal() {
postorderTraversal(root);
}
private void postorderTraversal(Node<E> node) {
if (node == null) return;
postorderTraversal(node.left);
postorderTraversal(node.right);
System.out.println(node.element);
}
/**
* 层序遍历
*/
public void levelOrderTraversal() {
if (root == null) return;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
System.out.println(node.element);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
public static abstract class Visitor<E> {
boolean stop;
/**
* @return 如果返回true，就代表停止遍历
*/
public abstract boolean visit(E element);
}
public void preorder(Visitor<E> visitor) {
if (visitor == null) return;
preorder(root, visitor);
}
private void preorder(Node<E> node, Visitor<E> visitor) {
if (node == null || visitor.stop) return;
visitor.stop = visitor.visit(node.element);
preorder(node.left, visitor);
preorder(node.right, visitor);
}
public void inorder(Visitor<E> visitor) {
if (visitor == null) return;
inorder(root, visitor);
}
private void inorder(Node<E> node, Visitor<E> visitor) {
if (node == null || visitor.stop) return;
inorder(node.left, visitor);
if (visitor.stop) return;
visitor.stop = visitor.visit(node.element);
inorder(node.right, visitor);
}
public void postorder(Visitor<E> visitor) {
if (visitor == null) return;
postorder(root, visitor);
}
private void postorder(Node<E> node, Visitor<E> visitor) {
if (node == null || visitor.stop) return;
postorder(node.left, visitor);
postorder(node.right, visitor);
if (visitor.stop) return;
visitor.stop = visitor.visit(node.element);
}
优化
public void levelOrder(Visitor<E> visitor) {
if (root == null || visitor == null) return;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
if (visitor.visit(node.element)) return;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
树状打印二叉树
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
toString(root, sb, "");
return sb.toString();
}
private void toString(Node<E> node, StringBuilder sb, String prefix) {
if (node == null) return;
toString(node.left, sb, prefix + "L---");
sb.append(prefix).append(node.element).append("/n");
toString(node.right, sb, prefix + "R---");
}
完全二叉树判断
public boolean isComplete() {
if (root == null) return false;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
boolean leaf = false;
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
if (leaf && !node.isLeaf()) return false;
if (node.left != null) {
queue.offer(node.left);
} else if (node.right != null) { // node.left == null && node.right != null
return false;
}
if (node.right != null) {
queue.offer(node.right);
} else { // node.right == null
leaf = true;
}
}
return true;
}
计算二叉树的高度
public int height() {
if (root == null) return 0;
// 树的高度
int height = 0;
// 存储着每一层的元素数量
int levelSize = 1;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
levelSize--;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
if (levelSize == 0) { // 意味着即将要访问下一层
levelSize = queue.size();
height++;
}
}
return height;
}
public int height2() {
return height(root);
}
private int height(Node<E> node) {
if (node == null) return 0;
return 1 + Math.max(height(node.left), height(node.right));
}
反转二叉树
package datastruct.tree.翻转二叉树;
import java.util.LinkedList;
import java.util.Queue;
public class invertTree {
// 首先我们考虑的不是用什么方式遍历的问题，而是考虑题目想要干什么
public TreeNode invertTree1(TreeNode root){
if (root == null) return root;
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree1(root.left);
invertTree1(root.right);
return root;
}
// public TreeNode invertTree(TreeNode root) {
// if (root == null) return root;
//
// TreeNode tmp = root.left;
// root.left = root.right;
// root.right = tmp;
//
// invertTree(root.left);
// invertTree(root.right);
//
// return root;
// }
// public TreeNode invertTree(TreeNode root) {
// if (root == null) return root;
//
// invertTree(root.left);
// invertTree(root.right);
//
// TreeNode tmp = root.left;
// root.left = root.right;
// root.right = tmp;
//
// return root;
// }
// public TreeNode invertTree(TreeNode root) {
// if (root == null) return root;
//
// invertTree(root.left);
//
// TreeNode tmp = root.left;
// root.left = root.right;
// root.right = tmp;
//
// invertTree(root.left);
//
// return root;
// }
// 层序遍历
public TreeNode invertTree(TreeNode root) {
if (root == null) return root;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
TreeNode tmp = node.left;
node.left = node.right;
node.right = tmp;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return root;
}
}
遍历应用
前序遍历
树状结构展示
中序遍历
二叉搜索树中序遍历按升序或者降序处理节点
后序遍历
先子后父
层序遍历
计算二叉树的高度
根据遍历结果重构二叉树
前序遍历 + 中序遍历
后序遍历 + 中序遍历
前序遍历 + 后序遍历
前+中
◼ 前序遍历：4 2 1 3 6 5 ◼ 中序遍历：1 2 3 4 5 6
前驱节点和后继节点
private Node<E> predecessor(Node<E> node) {
if (node == null) return null;
// 前驱节点在左子树当中（left.right.right.right....）
Node<E> p = node.left;
if (p != null) {
while (p.right != null) {
p = p.right;
}
return p;
}
// 从父节点、祖父节点中寻找前驱节点
while (node.parent != null && node == node.parent.left) {
node = node.parent;
}
// node.parent == null
// node == node.parent.right
return node.parent;
}
private Node<E> successor(Node<E> node) {
if (node == null) return null;
// 前驱节点在左子树当中（right.left.left.left....）
Node<E> p = node.right;
if (p != null) {
while (p.left != null) {
p = p.left;
}
return p;
}
// 从父节点、祖父节点中寻找前驱节点
while (node.parent != null && node == node.parent.right) {
node = node.parent;
}
return node.parent;
}
二叉搜索树
在 n 个动态的整数中搜索某个整数？（查看其是否存在）
◼ 针对这个需求，有没有更好的方案？
使用二叉搜索树，添加、删除、搜索的最坏时间复杂度均可优化至：O(logn)
0 1 2 3 4 5 6 7 8 9
31 66 17 15 28 20 59 88 45 56
◼ 如果维护一个有序的动态数组，使用二分搜索，最坏时间复杂度：O(logn)
但是添加、删除的平均时间复杂度是 O(n)
0 1 2 3 4 5 6 7 8 9
15 17 20 28 31 45 56 59 66 88
◼ 假设使用动态数组存放元素，从第 0 个位置开始遍历搜索，平均时间复杂度：O(n)
删除节点
删除度为0的节点，删除叶子节点
node == node.parent.left
✓ node.parent.left = null
node == node.parent.right
✓ node.parent.right = null
node.parent == null
✓ root = null
删除度为1的节点
用子节点替代源节点的位置
child 是 node.left 或者 child 是 node.right
用 child 替代 node 的位置
✓ 如果 node 是左子节点
➢ child.parent = node.parent
➢ node.parent.left = child
✓ 如果 node 是右子节点
➢ child.parent = node.parent
➢ node.parent.right = child
✓ 如果 node 是根节点
➢ root = child
➢ child.parent = null
删除度为2的节点(删除根节点)
◼ 举例：先删除 5、再删除 4
◼ 先用前驱或者后继节点的值覆盖原节点的值
◼ 然后删除相应的前驱或者后继节点
◼ 如果一个节点的度为 2，那么
它的前驱、后继节点的度只可能是 1 和 0
private void remove(Node<E> node) {
if (node == null) return;
size--;
if (node.hasTwoChildren()) { // 度为2的节点
// 找到后继节点
Node<E> s = successor(node);
// 用后继节点的值覆盖度为2的节点的值
node.element = s.element;
// 删除后继节点
node = s;
}
// 删除node节点（node的度必然是1或者0）
Node<E> replacement = node.left != null ? node.left : node.right;
if (replacement != null) { // node是度为1的节点
// 更改parent
replacement.parent = node.parent;
// 更改parent的left、right的指向
if (node.parent == null) { // node是度为1的节点并且是根节点
root = replacement;
} else if (node == node.parent.left) {
node.parent.left = replacement;
} else { // node == node.parent.right
node.parent.right = replacement;
}
} else if (node.parent == null) { // node是叶子节点并且是根节点
root = null;
} else { // node是叶子节点，但不是根节点
if (node == node.parent.left) {
node.parent.left = null;
} else { // node == node.parent.right
node.parent.right = null;
}
}
}
------------------------------
找后继节点代码
private Node<E> successor(Node<E> node) {
if (node == null) return null;
// 前驱节点在左子树当中（right.left.left.left....）
Node<E> p = node.right;
if (p != null) {
while (p.left != null) {
p = p.left;
}
return p;
}
// 从父节点、祖父节点中寻找前驱节点
while (node.parent != null && node == node.parent.right) {
node = node.parent;
}
return node.parent;
}
--------------
node
private Node<E> node(E element) {
Node<E> node = root;
while (node != null) {
int cmp = compare(element, node.element);
if (cmp == 0) return node;
if (cmp > 0) {
node = node.right;
} else { // cmp < 0
node = node.left;
}
}
return null;
}
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/281688.html