Problem：面试题 10.10. 数字流的秩
TreeMap 解法
由于 Java 内置的
TreeMap 类不支持自定义树的底层逻辑操作，故用 TreeMap 实际会导致调用 getRankOfNumber 方法时的时间复杂度退化到 。代码
Java
import java.util.TreeMap; class StreamRank { TreeMap<Integer, Integer> treeMap; public StreamRank() { treeMap = new TreeMap<>(); } public void track(int x) { treeMap.put(x, treeMap.getOrDefault(x, 0) + 1); } public int getRankOfNumber(int x) { int rank = 0; for (int v : treeMap.headMap(x, true).values()) { rank += v; } return rank; } }
复杂度分析
- 时间复杂度：
track方法的平均时间复杂度为 ，getRankOfNumber方法的时间复杂度可能会退化到 。其中 为当前数字流中数字的个数。
- 空间复杂度：。其中 为数字流中数字的总个数。
AVL Tree 解法
代码
Java
class StreamRank { DuplicatedLEAVLTree<Integer> tree; public StreamRank() { tree = new DuplicatedLEAVLTree<>(); } public void track(int x) { tree.add(x); } public int getRankOfNumber(int x) { return tree.headTreeSize(x, true); } /** * A avl tree that allows duplicated elements. It is rapid to get * the count of the elements that are less than or equal to the given value. */ public class DuplicatedLEAVLTree<T extends Comparable<T>> { private Node root; private class Node { public T val; public int height = 1, size = 1, count = 1; public Node parent, left, right; public Node(T val, Node parent) { this.val = val; this.parent = parent; } public int refreshSize() { size = size(left) + size(right) + count; return size; } public int refreshHeight() { height = Math.max(height(left), height(right)) + 1; return height; } public void refreshSizeAndHeight() { refreshSize(); refreshHeight(); } public int getBalanceFactor() { return height(left) - height(right); } } /** * Add an element to the tree. * @param val * @return existed or not */ public boolean add(T val) { Node node = search(val), parent = null; if (node != null) { node.count++; rebalance(node); return true; } node = root; while (node != null) { parent = node; node = val.compareTo(node.val) < 0 ? node.left : node.right; } if (parent == null) { root = new Node(val, parent); } else if (val.compareTo(parent.val) > 0) { parent.right = new Node(val, parent); rebalance(parent); } else { parent.left = new Node(val, parent); rebalance(parent); } return false; } /** * Get the count of the elements that are less than (or equals to, if * inclusive is {@code true}) the given value. * @param val * @param inclusive * @return {@code count} */ public int headTreeSize(T val, boolean inclusive) { Node node = floor(val); if (node == null) { return 0; } int ans = size(root) - size(root.right); Node pointer = root; while (pointer != node) { if (node.val.compareTo(pointer.val) < 0) { ans -= pointer.count + size(pointer.left.right); pointer = pointer.left; } else { ans += pointer.right.count + size(pointer.right.left); pointer = pointer.right; } } if (!inclusive && node.val.equals(val)) { ans -= node.count; } return ans; } /** * Searches the node for the value. * @param val * @return {@code null} or {@code node} */ public Node search(T val) { Node node = root; while (node != null && !node.val.equals(val)) { node = node.val.compareTo(val) > 0 ? node.left : node.right; } return node; } private void rebalance(Node node) { while (node != null) { int balanceFactor = node.getBalanceFactor(); if (balanceFactor == 2) { if (height(node.left.left) < height(node.left.right)) { rotateLeft(node.left); } node = rotateRight(node); } else if (balanceFactor == -2) { if (height(node.right.right) < height(node.right.left)) { rotateRight(node.right); } node = rotateLeft(node); } node.refreshSizeAndHeight(); if (node.parent == null) { root = node; } node = node.parent; } } private Node rotateLeft(Node node) { Node right = node.right; node.right = right.left; if (node.right != null) { node.right.parent = node; } right.left = node; right.parent = node.parent; node.parent = right; if (right.parent != null) { if (right.parent.left == node) { right.parent.left = right; } else { right.parent.right = right; } } node.refreshSizeAndHeight(); right.refreshSizeAndHeight(); return right; } private Node rotateRight(Node node) { Node left = node.left; node.left = left.right; if (node.left != null) { node.left.parent = node; } left.right = node; left.parent = node.parent; node.parent = left; if (left.parent != null) { if (left.parent.left == node) { left.parent.left = left; } else { left.parent.right = left; } } node.refreshSizeAndHeight(); left.refreshSizeAndHeight(); return left; } private Node floor(T val) { Node node = root; Node ans = null; while (node != null && !node.val.equals(val)) { if (node.val.compareTo(val) > 0) { node = node.left; } else { ans = node; node = node.right; } } return node == null ? ans : node; } private int height(Node node) { return node == null ? 0 : node.height; } private int size(Node node) { return node == null ? 0 : node.size; } } }
复杂度分析
- 时间复杂度：
track方法的平均时间复杂度为 ，getRankOfNumber方法的时间复杂度为 。其中 为当前数字流中数字的个数。
- 空间复杂度：。其中 为数字流中数字的总个数。
其他有关代码
朴素 BST Tree
Java
/** * The implement of a BST tree. */ public class BSTTree<T extends Comparable<T>> { private Node root; private class Node { public T val; public Node parent, left, right; public Node(T val, Node parent) { this.val = val; this.parent = parent; } } /** * Add a unduplicated element to the tree. * @param val * @return added or not */ public boolean add(T val) { Node node = search(val), parent = null; if (node != null) { return false; } node = root; while (node != null) { parent = node; node = val.compareTo(node.val) < 0 ? node.left : node.right; } if (parent == null) { root = new Node(val, parent); } else if (val.compareTo(parent.val) > 0) { parent.right = new Node(val, parent); } else { parent.left = new Node(val, parent); } return true; } /** * Remove a existed element from the tree. * @param val * @return removed or not */ public boolean remove(T val) { Node node = search(val); if (node == null) { return false; } remove(node); return true; } /** * Searches the node for the value. * @param val * @return {@code null} or {@code node} */ public Node search(T val) { Node node = root; while (node != null && val.compareTo(node.val) != 0) { node = val.compareTo(node.val) < 0 ? node.left : node.right; } return node; } private void remove(Node node) { if (node.left == null && node.right == null) { if (node.parent == null) { root = null; } else if (node == node.parent.left) { node.parent.left = null; } else { node.parent.right = null; } } else if (node.left == null ^ node.right == null) { Node replaceNode = node.left != null ? node.left : node.right; replaceNode.parent = node.parent; if (node.parent == null) { root = replaceNode; } else if (node == node.parent.left) { node.parent.left = replaceNode; } else { node.parent.right = replaceNode; } } else { Node maxLeft = node.left; while (maxLeft.right != null) { maxLeft = maxLeft.right; } node.val = maxLeft.val; remove(maxLeft); } } private int height(Node root) { if (root == null) { return 0; } return Math.max(height(root.left), height(root.right)) + 1; } }
朴素 AVL Tree
Java
/** * The implement of a AVL tree. */ public class AVLTree<T extends Comparable<T>> { private Node root; private class Node { public T val; public int height = 1; public Node parent, left, right; public Node(T val, Node parent) { this.val = val; this.parent = parent; } public int refreshHeight() { height = Math.max(height(left), height(right)) + 1; return height; } public int getBalanceFactor() { return height(left) - height(right); } } /** * Add a unduplicated element to the tree. * @param val * @return added or not */ public boolean add(T val) { Node node = search(val), parent = null; if (node != null) { return false; } node = root; while (node != null) { parent = node; node = val.compareTo(node.val) < 0 ? node.left : node.right; } if (parent == null) { root = new Node(val, parent); } else if (val.compareTo(parent.val) > 0) { parent.right = new Node(val, parent); rebalance(parent); } else { parent.left = new Node(val, parent); rebalance(parent); } return true; } /** * Remove a existed element from the tree. * @param val * @return removed or not */ public boolean remove(T val) { Node node = search(val); if (node == null) { return false; } remove(node); return true; } /** * Searches the node for the value. * @param val * @return {@code null} or {@code node} */ public Node search(T val) { Node node = root; while (node != null && val.compareTo(node.val) != 0) { node = val.compareTo(node.val) < 0 ? node.left : node.right; } return node; } private void remove(Node node) { if (node.left == null && node.right == null) { if (node.parent == null) { root = null; } else if (node == node.parent.left) { node.parent.left = null; rebalance(node.parent); } else { node.parent.right = null; rebalance(node.parent); } } else if (node.left == null ^ node.right == null) { Node replaceNode = node.left != null ? node.left : node.right; replaceNode.parent = node.parent; if (node.parent == null) { root = replaceNode; } else if (node == node.parent.left) { node.parent.left = replaceNode; rebalance(node.parent); } else { node.parent.right = replaceNode; rebalance(node.parent); } } else { Node maxLeft = node.left; while (maxLeft.right != null) { maxLeft = maxLeft.right; } node.val = maxLeft.val; remove(maxLeft); } } private void rebalance(Node node) { while (node != null) { int balanceFactor = node.getBalanceFactor(); if (balanceFactor == 2) { if (height(node.left.left) < height(node.left.right)) { rotateLeft(node.left); } node = rotateRight(node); } else if (balanceFactor == -2) { if (height(node.right.right) < height(node.right.left)) { rotateRight(node.right); } node = rotateLeft(node); } node.refreshHeight(); if (node.parent == null) { root = node; } node = node.parent; } } private Node rotateLeft(Node node) { Node right = node.right; node.right = right.left; if (node.right != null) { node.right.parent = node; } right.left = node; right.parent = node.parent; node.parent = right; if (right.parent != null) { if (right.parent.left == node) { right.parent.left = right; } else { right.parent.right = right; } } node.refreshHeight(); right.refreshHeight(); return right; } private Node rotateRight(Node node) { Node left = node.left; node.left = left.right; if (node.left != null) { node.left.parent = node; } left.right = node; left.parent = node.parent; node.parent = left; if (left.parent != null) { if (left.parent.left == node) { left.parent.left = left; } else { left.parent.right = left; } } node.refreshHeight(); left.refreshHeight(); return left; } private int height(Node node) { return node == null ? 0 : node.height; } }
BST Tree（适用于找第 K 大的值）
Java
/** * A BST tree easy to find the kth smallest element. */ public class KthBSTTree<T extends Comparable<T>> { private Node root; private class Node { public T val; public int size = 1; public Node parent, left, right; public Node(T val, Node parent) { this.val = val; this.parent = parent; } } /** * Add a unduplicated element to the tree. * @param val * @return added or not */ public boolean add(T val) { Node node = search(val), parent = null; if (node != null) { return false; } node = root; while (node != null) { node.size++; parent = node; node = val.compareTo(node.val) < 0 ? node.left : node.right; } if (parent == null) { root = new Node(val, parent); } else if (val.compareTo(parent.val) > 0) { parent.right = new Node(val, parent); } else { parent.left = new Node(val, parent); } return true; } /** * Remove a existed element from the tree. * @param val * @return removed or not */ public boolean remove(T val) { Node node = search(val); if (node == null) { return false; } node = root; while (val.compareTo(node.val) != 0) { node.size--; node = val.compareTo(node.val) < 0 ? node.left : node.right; } remove(node); return true; } /** * Get the kth smallest element from the tree. * @param k * @return {@code value} */ public T kthSmallest(int k) { Node node = root; int index = node.left == null ? 1 : node.left.size + 1; while (k != index) { if (index < k) { node = node.right; index += node.left == null ? 1 : node.left.size + 1; } else { node = node.left; index -= node.right == null ? 1 : node.right.size + 1; } } return node.val; } /** * Searches the node for the value. * @param val * @return {@code null} or {@code Node} */ public Node search(T val) { Node node = root; while (node != null && val.compareTo(node.val) != 0) { node = val.compareTo(node.val) < 0 ? node.left : node.right; } return node; } private void remove(Node node) { if (node.left == null && node.right == null) { if (node.parent == null) { root = null; } else if (node == node.parent.left) { node.parent.left = null; } else { node.parent.right = null; } } else if (node.left == null ^ node.right == null) { Node replaceNode = node.left != null ? node.left : node.right; replaceNode.parent = node.parent; if (node.parent == null) { root = replaceNode; } else if (node == node.parent.left) { node.parent.left = replaceNode; } else { node.parent.right = replaceNode; } } else { Node maxLeft = node.left; while (maxLeft.right != null) { maxLeft.size--; maxLeft = maxLeft.right; } node.size--; node.val = maxLeft.val; remove(maxLeft); } } private int height(Node root) { return root == null ? 0 : Math.max(height(root.left), height(root.right)) + 1; } }
AVL Tree（适用于找第 K 大的值）
Java
/** * A AVL tree easy to find the kth smallest element. */ public class KthAVLTree<T extends Comparable<T>> { private Node root; private class Node { public T val; public int height = 1, size = 1; public Node parent, left, right; public Node(T val, Node parent) { this.val = val; this.parent = parent; } public int refreshSize() { size = size(left) + size(right) + 1; return size; } public int refreshHeight() { height = Math.max(height(left), height(right)) + 1; return height; } public void refreshSizeAndHeight() { refreshSize(); refreshHeight(); } public int getBalanceFactor() { return height(left) - height(right); } } /** * Add a unduplicated element to the tree. * @param val * @return added or not */ public boolean add(T val) { Node node = search(val), parent = null; if (node != null) { return false; } node = root; while (node != null) { parent = node; node = val.compareTo(node.val) < 0 ? node.left : node.right; } if (parent == null) { root = new Node(val, parent); } else if (val.compareTo(parent.val) > 0) { parent.right = new Node(val, parent); rebalance(parent); } else { parent.left = new Node(val, parent); rebalance(parent); } return true; } /** * Remove a existed element from the tree. * @param val * @return removed or not */ public boolean remove(T val) { Node node = search(val); if (node == null) { return false; } remove(node); return true; } /** * Get the kth smallest element from the tree. * @param k * @return {@code value} */ public T kthSmallest(int k) { Node node = root; int index = size(node.left) + 1; while (k != index) { if (index < k) { node = node.right; index += size(node.left) + 1; } else { node = node.left; index -= size(node.right) + 1; } } return node.val; } /** * Searches the node for the value. * @param val * @return {@code null} or {@code node} */ public Node search(T val) { Node node = root; while (node != null && val.compareTo(node.val) != 0) { node = val.compareTo(node.val) < 0 ? node.left : node.right; } return node; } private void remove(Node node) { if (node.left == null && node.right == null) { if (node.parent == null) { root = null; } else if (node == node.parent.left) { node.parent.left = null; rebalance(node.parent); } else { node.parent.right = null; rebalance(node.parent); } } else if (node.left == null ^ node.right == null) { Node replaceNode = node.left != null ? node.left : node.right; replaceNode.parent = node.parent; if (node.parent == null) { root = replaceNode; } else if (node == node.parent.left) { node.parent.left = replaceNode; rebalance(node.parent); } else { node.parent.right = replaceNode; rebalance(node.parent); } } else { Node maxLeft = node.left; while (maxLeft.right != null) { maxLeft = maxLeft.right; } node.val = maxLeft.val; remove(maxLeft); } } private void rebalance(Node node) { while (node != null) { int balanceFactor = node.getBalanceFactor(); if (balanceFactor == 2) { if (height(node.left.left) < height(node.left.right)) { rotateLeft(node.left); } node = rotateRight(node); } else if (balanceFactor == -2) { if (height(node.right.right) < height(node.right.left)) { rotateRight(node.right); } node = rotateLeft(node); } node.refreshSizeAndHeight(); if (node.parent == null) { root = node; } node = node.parent; } } private Node rotateLeft(Node node) { Node right = node.right; node.right = right.left; if (node.right != null) { node.right.parent = node; } right.left = node; right.parent = node.parent; node.parent = right; if (right.parent != null) { if (right.parent.left == node) { right.parent.left = right; } else { right.parent.right = right; } } node.refreshSizeAndHeight(); right.refreshSizeAndHeight(); return right; } private Node rotateRight(Node node) { Node left = node.left; node.left = left.right; if (node.left != null) { node.left.parent = node; } left.right = node; left.parent = node.parent; node.parent = left; if (left.parent != null) { if (left.parent.left == node) { left.parent.left = left; } else { left.parent.right = left; } } node.refreshSizeAndHeight(); left.refreshSizeAndHeight(); return left; } private int height(Node node) { return node == null ? 0 : node.height; } private int size(Node node) { return node == null ? 0 : node.size; } }
AVL Tree（适用于找第 K 大的值、元素可重复）
Java
/** * A AVL tree allows the duplicated elements and is easy to find the kth smallest element. */ public class DuplicatedKthAVLTree<T extends Comparable<T>> { private Node root; private class Node { public T val; public int height = 1, size = 1, count = 1; public Node parent, left, right; public Node(T val, Node parent) { this.val = val; this.parent = parent; } public int refreshSize() { size = size(left) + size(right) + count; return size; } public int refreshHeight() { height = Math.max(height(left), height(right)) + 1; return height; } public void refreshSizeAndHeight() { refreshSize(); refreshHeight(); } public int getBalanceFactor() { return height(left) - height(right); } } /** * Add an element to the tree. * @param val * @return existed or not */ public boolean add(T val) { Node node = search(val), parent = null; if (node != null) { node.count++; rebalance(node); return true; } node = root; while (node != null) { parent = node; node = val.compareTo(node.val) < 0 ? node.left : node.right; } if (parent == null) { root = new Node(val, parent); } else if (val.compareTo(parent.val) > 0) { parent.right = new Node(val, parent); rebalance(parent); } else { parent.left = new Node(val, parent); rebalance(parent); } return false; } /** * Remove a existed element from the tree. * @param val * @return removed or not */ public boolean remove(T val) { Node node = search(val); if (node == null) { return false; } if (--node.count == 0) { remove(node); } else { rebalance(node); } return true; } /** * Get the kth smallest element from the tree. * @param k * @return {@code value} */ public T kthSmallest(int k) { Node node = root; int leftBound = size(node.left) + 1; int rightBound = leftBound + node.count - 1; while (k < leftBound || k > rightBound) { if (rightBound < k) { leftBound += node.count + size(node.right.left); node = node.right; } else { node = node.left; leftBound -= size(node.right) + node.count; } rightBound = leftBound + node.count - 1; } return node.val; } /** * Searches the node for the value. * @param val * @return {@code null} or {@code node} */ public Node search(T val) { Node node = root; while (node != null && val.compareTo(node.val) != 0) { node = val.compareTo(node.val) < 0 ? node.left : node.right; } return node; } private void remove(Node node) { if (node.left == null && node.right == null) { if (node.parent == null) { root = null; } else if (node == node.parent.left) { node.parent.left = null; rebalance(node.parent); } else { node.parent.right = null; rebalance(node.parent); } } else if (node.left == null ^ node.right == null) { Node replaceNode = node.left != null ? node.left : node.right; replaceNode.parent = node.parent; if (node.parent == null) { root = replaceNode; } else if (node == node.parent.left) { node.parent.left = replaceNode; rebalance(node.parent); } else { node.parent.right = replaceNode; rebalance(node.parent); } } else { Node maxLeft = node.left; while (maxLeft.right != null) { maxLeft = maxLeft.right; } node.val = maxLeft.val; remove(maxLeft); } } private void rebalance(Node node) { while (node != null) { int balanceFactor = node.getBalanceFactor(); if (balanceFactor == 2) { if (height(node.left.left) < height(node.left.right)) { rotateLeft(node.left); } node = rotateRight(node); } else if (balanceFactor == -2) { if (height(node.right.right) < height(node.right.left)) { rotateRight(node.right); } node = rotateLeft(node); } node.refreshSizeAndHeight(); if (node.parent == null) { root = node; } node = node.parent; } } private Node rotateLeft(Node node) { Node right = node.right; node.right = right.left; if (node.right != null) { node.right.parent = node; } right.left = node; right.parent = node.parent; node.parent = right; if (right.parent != null) { if (right.parent.left == node) { right.parent.left = right; } else { right.parent.right = right; } } node.refreshSizeAndHeight(); right.refreshSizeAndHeight(); return right; } private Node rotateRight(Node node) { Node left = node.left; node.left = left.right; if (node.left != null) { node.left.parent = node; } left.right = node; left.parent = node.parent; node.parent = left; if (left.parent != null) { if (left.parent.left == node) { left.parent.left = left; } else { left.parent.right = left; } } node.refreshSizeAndHeight(); left.refreshSizeAndHeight(); return left; } private int height(Node node) { return node == null ? 0 : node.height; } private int size(Node node) { return node == null ? 0 : node.size; } }
AVL Tree（适用于找中位数、元素可重复）
实际上找中位数可以通过调用最多两次找第 大的数的对应 AVL Tree 实现，但是这里还是给出只调用一次就能获得中位数的代码。
Java
public class DuplicatedMedianAVLTree<T extends Comparable<T>, E extends Comparable<E>> { private Node root; private Node lessThanEqualsMedian, greaterThanEqualsMedian; private int lessThanEqualsMedianCount = 1, greaterThanEqualsMedianCount = 1; private class Node { public T val; public int height = 1, size = 1, count = 1; public Node parent, left, right; public Node(T val, Node parent) { this.val = val; this.parent = parent; } public int refreshSize() { size = size(left) + size(right) + count; return size; } public int refreshHeight() { height = Math.max(height(left), height(right)) + 1; return height; } public void refreshSizeAndHeight() { refreshSize(); refreshHeight(); } public int getBalanceFactor() { return height(left) - height(right); } } /** * Add an element to the tree. * @param val * @return existed or not */ public boolean add(T val) { Node node = search(val), parent = null; if (node != null) { node.count++; rebalance(node); refreshMedian(val); return true; } node = root; while (node != null) { parent = node; node = val.compareTo(node.val) < 0 ? node.left : node.right; } if (parent == null) { root = new Node(val, parent); } else if (val.compareTo(parent.val) > 0) { parent.right = new Node(val, parent); rebalance(parent); } else { parent.left = new Node(val, parent); rebalance(parent); } refreshMedian(val); return false; } /** * Get the middle element from the tree. * @return {@code value} */ public E median(BiFunction<T, T, E> func) { return func.apply(lessThanEqualsMedian.val, greaterThanEqualsMedian.val); } /** * Searches the node for the value. * @param val * @return {@code null} or {@code node} */ public Node search(T val) { Node node = root; while (node != null && val.compareTo(node.val) != 0) { node = val.compareTo(node.val) < 0 ? node.left : node.right; } return node; } private void refreshMedian(T val) { if (root.size == 1) { lessThanEqualsMedian = root; greaterThanEqualsMedian = root; } else if (root.size % 2 == 0) { if (val.compareTo(lessThanEqualsMedian.val) >= 0) { greaterThanEqualsMedianCount++; if (greaterThanEqualsMedianCount > greaterThanEqualsMedian.count) { greaterThanEqualsMedian = higher(greaterThanEqualsMedian); greaterThanEqualsMedianCount = 1; } } else { lessThanEqualsMedianCount--; if (lessThanEqualsMedianCount < 1) { lessThanEqualsMedian = lower(lessThanEqualsMedian); lessThanEqualsMedianCount = lessThanEqualsMedian.count; } } } else { if (val.compareTo(lessThanEqualsMedian.val) >= 0) { lessThanEqualsMedianCount++; if (lessThanEqualsMedianCount > lessThanEqualsMedian.count) { lessThanEqualsMedian = higher(lessThanEqualsMedian); lessThanEqualsMedianCount = 1; } } if (val.compareTo(greaterThanEqualsMedian.val) < 0) { greaterThanEqualsMedianCount--; if (greaterThanEqualsMedianCount < 1) { greaterThanEqualsMedian = lower(greaterThanEqualsMedian); greaterThanEqualsMedianCount = greaterThanEqualsMedian.count; } } } } private void rebalance(Node node) { while (node != null) { int balanceFactor = node.getBalanceFactor(); if (balanceFactor == 2) { if (height(node.left.left) < height(node.left.right)) { rotateLeft(node.left); } node = rotateRight(node); } else if (balanceFactor == -2) { if (height(node.right.right) < height(node.right.left)) { rotateRight(node.right); } node = rotateLeft(node); } node.refreshSizeAndHeight(); if (node.parent == null) { root = node; } node = node.parent; } } private Node rotateLeft(Node node) { Node right = node.right; node.right = right.left; if (node.right != null) { node.right.parent = node; } right.left = node; right.parent = node.parent; node.parent = right; if (right.parent != null) { if (right.parent.left == node) { right.parent.left = right; } else { right.parent.right = right; } } node.refreshSizeAndHeight(); right.refreshSizeAndHeight(); return right; } private Node rotateRight(Node node) { Node left = node.left; node.left = left.right; if (node.left != null) { node.left.parent = node; } left.right = node; left.parent = node.parent; node.parent = left; if (left.parent != null) { if (left.parent.left == node) { left.parent.left = left; } else { left.parent.right = left; } } node.refreshSizeAndHeight(); left.refreshSizeAndHeight(); return left; } private Node higher(Node node) { if (node.right != null) { node = node.right; while (node.left != null) { node = node.left; } } else { while (node.parent != null && (node.parent.left == null || node.parent.left != node)) { node = node.parent; } node = node.parent; } return node; } private Node lower(Node node) { if (node.left != null) { node = node.left; while (node.right != null) { node = node.right; } } else { while (node.parent != null && (node.parent.right == null || node.parent.right != node)) { node = node.parent; } node = node.parent; } return node; } private int height(Node node) { return node == null ? 0 : node.height; } private int size(Node node) { return node == null ? 0 : node.size; } }
附录
比较漂亮地打印一棵树（方便查找错误）。
Java
class xxxxxx { .... other codes .... /** * Print the view of the tree nodes' size. */ public void printSize() { print(node -> node.size); } /** * Print the view of the tree. */ public void print() { print(node -> node.val); } private void print(Function<Node, ?> targetFunction) { /** The max decimal bits' length of the max value. */ /** e.g. 9-1, 99-2, 999-3, 99999999-8 */ int MAX_VAL_SIZE = 3; int height = height(root); int m = (int) Math.pow(2, height - 1) * MAX_VAL_SIZE * 2; Queue<Node> queue = new LinkedList<>(); Queue<Integer> rank = new LinkedList<>(); if (root != null) { queue.add(root); rank.add(1); } for (int nodeSize = 1; !queue.isEmpty(); nodeSize <<= 1) { StringBuilder branches = new StringBuilder(); StringBuilder vals = new StringBuilder(); branches.append(" ".repeat(m / nodeSize / 2 - MAX_VAL_SIZE / 2)); vals.append(" ".repeat(m / nodeSize / 2 - MAX_VAL_SIZE / 2)); for (int i = 1, size = queue.size(); i <= nodeSize; i++) { if (size == 0 || i < rank.peek()) { branches.append(" ".repeat(MAX_VAL_SIZE)); vals.append(" ".repeat(MAX_VAL_SIZE)); } else { size--; Node node = queue.poll(); if (rank.poll() % 2 == 1) { branches.append(String.format("%" + MAX_VAL_SIZE + "s", "/" + "-".repeat(MAX_VAL_SIZE - 1 >> 1))); vals.append(String.format("%-" + MAX_VAL_SIZE + "s", targetFunction.apply(node))); } else { branches.append(String.format("%-" + MAX_VAL_SIZE + "s", "-".repeat(MAX_VAL_SIZE - 1 >> 1) + "\\")); vals.append(String.format("%" + MAX_VAL_SIZE + "s", targetFunction.apply(node))); } if (node.left != null) { queue.add(node.left); rank.add(i * 2 - 1); } if (node.right != null) { queue.add(node.right); rank.add(i * 2); } } if (i % 2 == 1) { branches.append("-".repeat(m / nodeSize - MAX_VAL_SIZE)); } else { branches.append(" ".repeat(m / nodeSize - MAX_VAL_SIZE)); } vals.append(" ".repeat(m / nodeSize - MAX_VAL_SIZE)); } if (nodeSize == 1) { System.out.println(vals.toString()); } else { System.out.println(branches.append('\n').append(vals).toString()); } } } }
待补充….
暂时只写完整了这些与 AVL Tree 相关的树及其变种，其它有机会再补充。