使用BST插入法查询进行升序和降序排序

Question

我想按紧急数据字段的降序向 BST 中插入一个新对象 newPat 作为二进制节点。我正在按升序执行以下代码。如何将其更改为降序？

英国夏令时 class:

public void insertPatient(Patient newPat)
{
    BNode temp = new BNode(newPat);
    root = insert(root, temp);
}


protected BNode insert(BNode rt, BNode newNode)
{
    //attach newnode to correct subtree keeping ascending order and returns pointer to the node which it was called
    if(rt == null){
        rt = newNode; //last node becomes root           
    }else 
    {
        if((newNode.obj.getKey().compareTo(rt.obj.getKey()) < 0))
        {
            rt.left = insert (rt.left, newNode);
        } 
        else 
        {
            rt.right = insert (rt.right, newNode);
        }
    }
    return rt;
}

Answer 1

在二叉搜索树中（按照常识），root 不会是最小值或最大值（除非您的插入顺序确保或执行轮换来管理属性。在这种情况下, 它会有最坏情况的时间复杂度)
如果您总是需要最小值或最大值，请尝试查看 Binomial Heap

根据作者的说明更新

由于现有代码将 lesser 值插入 left 子树并将 bigger 值插入右子树，因此将 < 更改为 >= 应该解决您的用例。

    protected BNode insert(BNode parent, BNode newNode) {
        if (parent == null) {
            return newNode;
        }
        if (newNode.obj.getKey().compareTo(parent.obj.getKey()) >= 0) {
            parent.left = insert (parent.left, newNode);
        } else {
            parent.right = insert (parent.right, newNode);
        }
        return parent;
    }

使用 descending 的这个新属性，确保将您的搜索功能也从 < 更新到 >=。否则插入将起作用并且搜索将无法识别该节点。

建议

或者，插入顺序可以保持不变，检索逻辑可以更改为遍历 (ascending) 树，从 right 到 left 以获得相同的行为。

保持现有代码用于插入（< 比较）

    protected List<Patient> descendingInorder(BNode node, List<Patient> values) {
        if (node == null) {
            return values;
        }
        descendingInorder(node.right, values);
        values.add(node.obj);
        descendingInorder(node.left, values);
        return values;
    }

备注

如果树可以包含重复项，则确保为其定义行为。

使用BST插入法查询进行升序和降序排序

Ascending and descending sorting using BST insert method query

java

binary-search-tree

nodes

根据作者的说明更新

建议

备注