插入二进制搜索树（BST）时计算较小值的数量

小编典典

插入二进制搜索树（BST）时计算较小值的数量

algorithm

我当前正在实现一种算法，在该算法中，我需要知道从已读取的数字中，有多少个数字小于当前正在处理的数字。

一种方法是通过合并排序，但是我对BST方法更感兴趣。

此过程旨在计算O(log n)值小于关键节点值的节点数：

countLessThan(int x, node T)
    if T = null
        return
    if T.value >= x
        countLessThan(x, T.left) // T.left contains only numbers < T.value and T.right only numbers > T.value
    else
        globalResult += T.numLeft
        countLessThan(x, T.right)

numLeft在这种情况下，该字段将存储在每个节点中，并表示其左侧子树（包括其自身）中的节点数。

所以我的问题是，如何快速更新此特定字段？

阅读 280

2020-07-28

共1个答案

小编典典

您可以在每个节点中存储连接到左侧（小于）的叶子数，并在插入新叶子时增加在左侧传递的每个分支的计数。

通过将插入时在右侧传递的所有分支计数相加，可以同时计算小于新插入值的值数。

下面是一个JavaScript代码片段来演示该方法：

function CountTree() {                           // tree constructor

    this.root = null;



    this.insert = function(value) {

        var branch = null, node = this.root, count = 0, after;

        while (node != null) {                   // traverse tree to find position

            branch = node;

            after = value > node.value;          // compare to get direction

            if (after) {

                node = branch.right;             // pass on the right (greater)

                count += branch.count;           // add all nodes to the left of branch

            } else {

                node = branch.left;              // pass on the left (smaller or equal)

                ++branch.count;                  // increment branch's count

            }

        }                                        // attach new leaf

        if (branch == null) this.root = new Leaf(value);

        else if (after) branch.right = new Leaf(value);

        else branch.left = new Leaf(value);

        return count;

    }



    function Leaf(value) {                       // leaf constructor

        this.value = value;

        this.left = null;

        this.right = null;

        this.count = 1;

    }

}



var t = new CountTree(), v = [5, 3, 8, 2, 4, 7, 9, 1, 4, 7, 8];

for (var i in v) {

    document.write("Inserting " + v[i] + " (found " + t.insert(v[i]) + " smaller)<BR>");

}

这是代码示例中的树，当插入最后一个元素（第二个值8）时。每个节点的左侧顶点（包括其自身）的节点数打印在其右侧顶点的下方。当插入第二个8时，传递值为5、8和7的节点。其中，5和7在右侧传递，它们的计数之和为6
+ 2 = 8，所以在树中有8个比8小的值：1、2、3、4、4、5、7 7.第一个值为8的节点在左侧传递，因此其计数将从3递增到4。

2020-07-28