基于价格排序的二叉树中查找指定条件的最优Order对象

定义与需求 #

POJO定义 #

public class Order {
  int price;
  int size;
  boolean isBid;
}

核心需求 #

实现两个方法：

• 方法1：返回isBid=true且价格最高的Order（最优买入单）
• 方法2：返回isBid=false且价格最低的Order（最优卖出单）

前置说明 #

1. 市场订单簿规则：所有isBid=true的订单价格不会高于isBid=false的订单价格
2. 当前采用基于价格排序的二叉树存储，新增节点方法如下：

private Node updateOrderBook(Node current,Order order) {
  if (current == null) {
    return new Node(order);
  }
  if (order.getPrice() < current.order.getPrice()) {
    current.left = updateOrderBook(current.left,order);
  } else if (order.getPrice() > current.order.getPrice()) {
    current.right = updateOrderBook(current.right,order);
  } else {
    current.order.setSize(order.getSize());
  }
  return current;
}

当前实现问题 #

现有findBestBid方法在遍历到卖出单（Ask）时无法定位到最后一个有效买入单（Bid），逻辑存在漏洞：

private Order findBestBid(Node current) {
    if (current == null) {
      return null;
    }

    if (current.order.isBid() && current.right == null) {
      return current.order;
    }
    
    return current.order.isBid()
        ? findBestBid(current.right)
        : findBestBid(current.left);
}

解决方案 #

1. 修正最优买入单（findBestBid）方法 #

核心逻辑：利用Bid价格≤Ask价格的规则，优先向右遍历寻找更高价格的订单，同时记录遍历路径中最后一个有效Bid。

private Order findBestBid(Node current) {
    if (current == null) {
        return null;
    }
    // 先向右找更高价格的订单，优先返回右子树的有效Bid
    Order rightBid = findBestBid(current.right);
    if (rightBid != null) {
        return rightBid;
    }
    // 右子树无有效Bid，检查当前节点是否为Bid
    if (current.order.isBid()) {
        return current.order;
    }
    // 当前节点不是Bid，向左继续查找
    return findBestBid(current.left);
}

2. 实现最优卖出单（findBestAsk）方法 #

同理，优先向左遍历寻找更低价格的订单，记录路径中最后一个有效Ask：

private Order findBestAsk(Node current) {
    if (current == null) {
        return null;
    }
    // 先向左找更低价格的订单，优先返回左子树的有效Ask
    Order leftAsk = findBestAsk(current.left);
    if (leftAsk != null) {
        return leftAsk;
    }
    // 左子树无有效Ask，检查当前节点是否为Ask
    if (!current.order.isBid()) {
        return current.order;
    }
    // 当前节点不是Ask，向右继续查找
    return findBestAsk(current.right);
}

数据结构优化建议 #

二叉树实现虽可行，但订单簿场景下更推荐拆分存储+有序集合方案：

• 买入单（Bid）用降序TreeMap存储，键为价格，值为对应Order，直接取第一个元素就是最高价格Bid
• 卖出单（Ask）用升序TreeMap存储，直接取第一个元素就是最低价格Ask
  该方案查询效率更高（O(logn)），实现更简洁，避免二叉树遍历的逻辑漏洞。

示例代码：

// 买入单：价格降序排列
private TreeMap<Integer, Order> bidMap = new TreeMap<>(Collections.reverseOrder());
// 卖出单：价格升序排列
private TreeMap<Integer, Order> askMap = new TreeMap<>();

// 更新订单方法
private void updateOrderBook(Order order) {
    if (order.isBid()) {
        bidMap.put(order.price, order);
    } else {
        askMap.put(order.price, order);
    }
}

// 查询最优Bid
private Order findBestBid() {
    return bidMap.isEmpty() ? null : bidMap.firstEntry().getValue();
}

// 查询最优Ask
private Order findBestAsk() {
    return askMap.isEmpty() ? null : askMap.firstEntry().getValue();
}

内容的提问来源于stack exchange，提问作者Данил Денк