首页 algorithm tree

# 定义

  1. 是一棵二叉树；每个结点都有一个可比较的键，以及关联的值。
  2. 任何结点中的键大于该结点左子树中所有结点中的键，且小于该结点右子树中所有结点的键（有序性）
    有序性

# 遍历

主要讨论的是深度遍历，根据根结点的访问优先级，又可以分为：前（先）、中、后序遍历。

获取结点的前驱后继时，需要用到这部分知识点，而且平衡树的调整操作中也涉及到。

# 前序遍历

前（先）序遍历（Pre-Order Traversal）：先根结点，再左右子树。

前序遍历

# 中序遍历

中序遍历（In-Order Traversal）：先左子树，再根结点，最后右子树。

中序遍历

# 后序遍历

后序遍历（Post-Order Traversal）：先左右子树，再根结点。

后序遍历

# 代码实现：递归

# 前序遍历

public void preOrderTraversalRecursion(Node node, List<K> result) {
    if (node == null) {
        return;
    }
    // 先根结点
    result.add((K) node.key);
    // 再左右子树
    if (node.left != null) {
        preOrderTraversalRecursion(node.left, result);
    }
    if (node.right != null) {
        preOrderTraversalRecursion(node.right, result);
    }
}

# 中序遍历

public void inOrderTraversalRecursion(Node node, List<K> result) {
    if (node == null) {
        return;
    }
    // 先左子树
    if (node.left != null) {
        inOrderTraversalRecursion(node.left, result);
    }
    // 再根结点
    result.add((K) node.key);
    // 后右子树
    if (node.right != null) {
        inOrderTraversalRecursion(node.right, result);
    }
}

# 后序遍历

public void postOrderTraversalRecursion(Node node, List<K> result) {
    if (node == null) {
        return;
    }
    // 先左子树
    if (node.left != null) {
        postOrderTraversalRecursion(node.left, result);
    }
    // 再右子树
    if (node.right != null) {
        postOrderTraversalRecursion(node.right, result);
    }
    // 后根结点
    result.add((K) node.key);
}

# 代码实现：非递归

# 前序遍历

实现关键：

  1. 使用栈结构，根结点入栈；循环条件：栈非空。
  2. 出栈访问结点，右、左子树入栈
public void preOrderTraversalCirculation(Node root, List<K> result) {
    if (root == null) {
        return;
    }
    Deque<Node> stack = new ArrayDeque<>();
    // 1. 根结点入栈
    stack.push(root);
    // 2. 循环条件：栈非空
    while (!stack.isEmpty()) {
        // 3. 出栈访问根结点
        Node p = stack.pop();
        // 先访问根结点
        result.add((K) p.key);
        // 4. 再把右结点入栈：先进后出
        if (p.right != null) {
            stack.push(p.right);
        }
        // 5. 最后把左结点入栈：后进先出
        if (p.left != null) {
            stack.push(p.left);
        }
    }
}
# 中序遍历
实现关键：
  1. 使用栈结构，p 指向根结点
  2. 循环条件栈或 p 非空；遍历 p 左子树，遍历期间 p 入栈；出栈访问结点，p 指向右子树
public void inOrderTraversalCirculation(Node root, List<K> result) {
    if (root == null) {
        return;
    }
    Deque<Node> stack = new ArrayDeque<>();
    Node p = root;
    // 1. p 用于循环遍历左子树
    // 2. stack 用于回溯，记录 p 指针经过的结点
    while (!stack.isEmpty() || p != null) {
        // 访问最左边的左结点，栈记录经过的结点，用于回溯
        while (p != null) {
            stack.push(p);
            p = p.left;
        }
        // 出栈的结点，左子树都是已访问的
        p = stack.pop();
        // 访问中间结点
        result.add((K) p.key);
        // 循环访问右结点
        p = p.right;
    }
}
# 后序遍历
# 双栈实现
实现关键：
  1. 双栈结构，根结点入栈 1
  2. 循环条件栈 1 非空，栈 1 出栈入栈 2，左、右子树入栈 1
  3. 栈 2 依次出栈访问结点
public void postOrderTraversalCirculation1(Node root, List<K> result) {
    if (root == null) {
        return;
    }
    Deque<Node> stack1 = new ArrayDeque<>();
    Deque<Node> stack2 = new ArrayDeque<>();
    stack1.push(root);
    while (!stack1.isEmpty()) {
        Node node = stack1.pop();
        stack2.push(node);
        if (node.left != null) {
            stack1.push(node.left);
        }
        if (node.right != null) {
            stack1.push(node.right);
        }
    }
    while (!stack2.isEmpty()) {
        result.add((K) stack2.pop().key);
    }
}
# 单栈实现
实现关键：
  1. 栈结构，p 指向 root，p 入栈
  2. 循环条件栈非空；查看栈顶结点
public void postOrderTraversalCirculation2(Node root, List<K> result) {
    if (root == null) {
        return;
    }
    Deque<Node> stack = new ArrayDeque<>();
    Node p = root;
    stack.push(p);
    while (!stack.isEmpty()) {
        Node node = stack.peek();
        // 因为先访问底层，再访问上一层，所以直接判断左右子树是否等于 p
        boolean finishedSubtrees = (node.right == p || node.left == p);
        boolean isLeaf = (node.left == null && node.right == null);
        // 如果左右子树已经访问，或是叶子结点，直接访问
        if (finishedSubtrees || isLeaf) {
            stack.pop();
            result.add((K) node.key);
            p = node;
        } else { // 否则把右左子树入栈
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }
}
# 前驱后继
# 定义
# 前驱
比该结点的键小且最大的结点。
  1. 该结点有左子树：沿着左结点的右子树；循环到结点没有右子树，则该结点是前驱结点（左结点最右子树）。
    前驱：情形一
  2. 该结点没有左子树：沿着祖先结点往上查；循环到祖先结点的右结点等于上一轮循环的结点（查祖辈且出现拐角）。
    前驱：情形二
# 后继
比该结点的键大且最小的结点。
  1. 该结点有右子树：沿着右结点的左子树；循环到结点没有左子树，则该结点是前驱结点（右结点最左子树）。
    后继：情形一
  2. 该结点没有右子树：沿着父结点往上查；循环到祖先结点的左结点等于上一轮循环的结点（查祖辈且出现拐角）。
    后继：情形二
# 代码实现
# 前驱
Node 对象没有定义 parent 指针，无法向上遍历，因此需要借助栈记录祖先结点，然后通过栈回溯祖先结点。
如果 Node 定义 parent 属性，则很容易向上遍历，不需要借助栈回溯。
public Node predecessor(K key) {
    if (key == null) {
        throw new IllegalArgumentException("key can not be null.");
    }
    // 栈用于辅助回溯祖先结点；查找结点位置时，记录经过的祖先结点
    // 如果 Node 对象有 parent 指针时，则不需要额外的栈来向上查询祖先结点
    Deque<Node> stack = new ArrayDeque<>();
    Node p = root;
    // 找到结点位置
    while (p != null) {
        int cmp = key.compareTo((K) p.key);
        if (cmp < 0) {
            // 记录父结点
            stack.push(p);
            p = p.left;
        } else if (cmp > 0) {
            // 记录父结点
            stack.push(p);
            p = p.right;
        } else {
            // 找到结点
            break;
        }
    }
    // 0. 没找到结点
    if (p == null) {
        return null;
    }
    // 1. 有左子树：前驱结点在左结点的最右子树下
    if (p.left != null) {
        p = p.left;
        while (p.right != null) {
            p = p.right;
        }
        return p;
    }
    // 2. 没有左子树：借助栈回溯祖先结点；因为 Node 没有 parent 指针，无法向上遍历父结点
    while (!stack.isEmpty()) {
        // 回溯祖先结点
        Node q = stack.pop();
        /* q ->  6
         *        \
         *         9   <- p
         *        /
         *       8    key
         */
        if (q.right == p) {
            return q;
        } else {
            p = q;
        }
    }
    // 3. 没有前驱结点
    return null;
}
# 后继
借助栈记录祖先结点，然后通过栈回溯祖先结点。
public Node successor(K key) {
    if (key == null) {
        throw new IllegalArgumentException("key can not be null.");
    }
    // 栈用于辅助回溯祖先结点；查找结点位置时，记录经过的祖先结点
    // 如果 Node 对象有 parent 指针时，则不需要额外的栈来向上查询祖先结点
    Deque<Node> stack = new ArrayDeque<>();
    Node p = root;
    // 找到结点位置
    while (p != null) {
        int cmp = key.compareTo((K) p.key);
        if (cmp < 0) {
            // 记录父结点
            stack.push(p);
            p = p.left;
        } else if (cmp > 0) {
            // 记录父结点
            stack.push(p);
            p = p.right;
        } else {
            // 找到结点
            break;
        }
    }
    // 0. 没找到结点
    if (p == null) {
        return null;
    }
    // 1. 有右子树：后继结点在右结点的最左子树下
    if (p.right != null) {
        p = p.right;
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }
    // 2. 没有右子树：借助栈回溯祖先结点；因为 Node 没有 parent 指针，无法向上遍历父结点
    while (!stack.isEmpty()) {
        // 回溯祖先结点
        Node q = stack.pop();
        /* q ->  8
         *      /
         *     5   <- p
         *      \
         *       6    key
         */
        if (q.left == p) {
            return q;
        } else {
            p = q;
        }
    }
    // 3. 没有后继结点
    return null;
}
# 插入
# 插入情形
  1. 根结点为 null，未初始化：创建新结点，直接赋值给 root。
  2. 在左 / 右结点为 null 的位置插入。
插入
# 代码实现
public V put(K key, V value) {
    if (key == null) {
        throw new IllegalArgumentException("key can not be null.");
    }
    //p 指针用于遍历，寻找插入位置
    Node p = root;
    //parent 指针用于记录插入位置的父结点
    Node parent = null;
    while (p != null) {
        int cmp = key.compareTo((K) p.key);
        if (cmp < 0) {
            parent = p;
            p = p.left;
        } else if (cmp > 0) {
            parent = p;
            p = p.right;
        } else { // 更新
            V oldValue = (V) p.value;
            p.value = value;
            // 返回旧值
            return oldValue;
        }
    }
    // 1. 根结点初始化（第一次插入）：parent 为空
    if (parent == null) {
        root = new Node(key, value);
        return null;
    }
    // 2. 在左 / 右结点插入：
    if (key.compareTo((K) parent.key) < 0) {
        parent.left = new Node(key, value);
    } else {
        parent.right = new Node(key, value);
    }
    return null;
}
# 删除
# 删除情形
  1. 删除结点有左 + 右子树：转化为后 2 种情形。
    删除情形1-1
    删除情形1-2
  2. 删除叶子结点：直接删除。
    删除情形2-1
    删除情形2-2
  3. 删除只有一个子树的结点：删除结点的子树挂到父结点下。
    删除情形3-1
    删除情形3-2
# 代码实现
public V remove(K key) {
    if (key == null) {
        throw new IllegalArgumentException("key can not be null.");
    }
    //parent 指针记录删除结点的父结点
    Node parent = null;
    //p 指针查询删除结点位置
    Node p = root;
    while (p != null) {
        int cmp = key.compareTo((K) p.key);
        if (cmp < 0) {
            parent = p;
            p = p.left;
        } else if (cmp > 0) {
            parent = p;
            p = p.right;
        } else {
            break;
        }
    }
    // 0. 没找到结点
    if (p == null) {
        return null;
    }
    // 删除结点后返回旧值
    V oldValue = (V) p.value;
    // 1. 有 2 个子树的结点：找到后继结点替换，然后删除后继结点
    // 转化为：a. 删除叶子结点；b. 只有一个子树的结点
    if (p.left != null && p.right != null) {
        Node q = p.right; // 在右子树下查找后继结点
        parent = p;
        while (q.left != null) {
            parent = q;
            q = q.left;
        }
        // 用后继结点替换删除结点
        p.key = q.key;
        p.value = q.value;
        // 转化为删除后继结点；后继结点：1. 只有一个子树；2. 没有子树（叶子结点）
        p = q;
    }
    // 2. 叶子结点：直接删除
    if (p.left == null && p.right == null) {
        // 2_1. 删除根结点，且只有一个结点
        if (parent == null) {
            root = null;
            return oldValue;
        }
        // 2_2. 叶子结点直接从父结点中移除，得判断是在左还是右结点
        if (parent.left == p) { //p 是删除结点
            parent.left = null;
        } else if (parent.right == p) {
            parent.right = null;
        }
        return oldValue;
    }
    // 3. 只有 1 个子树的结点：删除结点的子树挂到父结点下
    // 3_1. 删除的是根结点，但有一个子结点：子结点直接作为根结点
    if (parent == null) {
        root = p.left == null ? p.right : p.left;
        // for gc
        p.left = p.right = null;
        return oldValue;
    }
    // 3_2. 删除的是非根结点：子树直接移到父结点的左 / 右孩子下
    if (parent.left == p) { //p 是删除结点
        parent.left = p.left != null ? p.left : p.right;
    } else {
        parent.right = p.left != null ? p.left : p.right;
    }
    // for gc
    p.left = p.right = null;
    return oldValue;
}
# 查找
public V get(K key) {
    if (key == null) {
        throw new IllegalArgumentException("key can not be null.");
    }
    Node node = getNode(key);
    return node == null ? null : (V) node.value;
}
public Node getNode(K key) {
    Node p = root;
    while (p != null) {
        int cmp = key.compareTo((K) p.key);
        if (cmp < 0) {
            p = p.left;
        } else if (cmp > 0) {
            p = p.right;
        } else {
            return p;
        }
    }
    return null;
}
# 空间复杂度
平均、最差：O(n)O(n)
# 时间复杂度
  1. 搜索、插入、删除，平均：O(log⁡n)O(\log n)
  2. 搜索、插入、删除，最差：O(n)O(n)
# 缺点
数据倾斜，退化为链表，时间复杂度最差：O(n)O(n)
数据倾斜