package CSC3100;

import java.util.*;

class TreeNode {
    long val;
    TreeNode left, right;

    public TreeNode(long val) {
        this.val = val;
        this.left = this.right = null;
    }
}

public class BST {
    private TreeNode root;

    public BST() {
        this.root = null;
    }

    // Function to insert a value into the BST
    public void insert(long value) {
        root = insertRec(root, value);
    }

    private TreeNode insertRec(TreeNode root, long value) {
        if (root == null) {
            root = new TreeNode(value);
            return root;
        }

        if (value <= root.val) {
            root.left = insertRec(root.left, value);
        } else if (value > root.val) {
            root.right = insertRec(root.right, value);
        }

        return root;
    }

    // Function to find the predecessor of a value in the BST
    public long predecessor(long value) {
        TreeNode predecessor = null;
        TreeNode current = root;

        while (current != null) {
            if (current.val <= value) {
                predecessor = current;
                current = current.right;
            } else {
                current = current.left;
            }
        }

        return (predecessor != null) ? predecessor.val : Integer.MIN_VALUE;
    }

    // Function to find the successor of a value in the BST
    public long successor(long value) {
        TreeNode successor = null;
        TreeNode current = root;

        while (current != null) {
            if (current.val > value) {
                successor = current;
                current = current.left;
            } else {
                current = current.right;
            }
        }

        return (successor != null) ? successor.val : Integer.MAX_VALUE;
    }

    private static void buyBook(List<Long> prices, Stack<Long> adjacentDifferences, Stack<Long> differences,BST pricesTree, long x) {
        long lastPrice = prices.get(prices.size() - 1);
        long  adjDiff = Math.abs(x - lastPrice);
        if (adjDiff < adjacentDifferences.peek()) {
            adjacentDifferences.push(adjDiff);
        }
        prices.add(x);
        long pred = pricesTree.predecessor(x);
        long succ = pricesTree.successor(x);

        long diff1 = Math.abs(pred - x);
        long diff2 = Math.abs(x - succ);
        long diff = Math.min(diff1, diff2);

        if (diff < differences.peek()) {
            differences.push(diff);
        }
        pricesTree.insert(x);
    }

    private static long closestAdjacentPrice(Stack<Long> adjacentDifferences) {
        return adjacentDifferences.peek();
    }

    private static long closestPrice(Stack<Long> differences) {
        return differences.peek();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long m = scanner.nextLong();
        List<Long> prices = new ArrayList<>();
        BST pricesTree = new BST();
        Stack<Long> adjacentDifferences = new Stack<>();
        Stack<Long> differences = new Stack<>();

        long val = Integer.MAX_VALUE;
        adjacentDifferences.push(val);

        for (long i = 0; i < n; i++) {
            long price = scanner.nextLong();
            pricesTree.insert(price);
            prices.add(price);

            if (i > 0) {
                long diff = Math.abs(price - prices.get((int) i - 1));
                if (diff < adjacentDifferences.peek()) {
                    adjacentDifferences.push(diff);
                }
            }
        }

        differences.push(adjacentDifferences.peek());
        List<Long> temp = new ArrayList<>(prices);
        Collections.sort(temp); // Sort the prices initially
        for (int i = 1; i < temp.size(); i++) {
            long diff = Math.abs(temp.get(i) - temp.get(i - 1));
            if (diff < differences.peek()) {
                differences.push(diff);
            }
        }

        Queue<Long> results = new LinkedList<>();
        for (long i = 0; i < m; i++) {
            String operation = scanner.next();
            switch (operation) {
                case "BUY" -> {
                    long x = scanner.nextLong();
                    buyBook(prices, adjacentDifferences, differences, pricesTree, x);
                }
                case "CLOSEST_ADJ_PRICE" -> {
                    long result = closestAdjacentPrice(adjacentDifferences);
                    results.add(result);
                }
                case "CLOSEST_PRICE" -> {
                    long result = closestPrice(differences);
                    results.add(result);
                }
            }
        }

        scanner.close();
        while (!results.isEmpty()) {
            System.out.println(results.poll());
        }
    }
}解释这个程序