二进制搜索树JavaScript实现 - 删除功能

Question

这是我在JavaScript中使用二进制搜索树的实现.除功能外,所有功能似乎都正常工作remove.具体来说,它似乎正在正确删除节点,直到树中剩下2个节点:

var binaryTreeNode = function (value) {
  return {
    value : value,
    left  : null,
    right : null
  };
};

var binarySearchTree = function () {
  var tree  = Object.create( binarySearchTreeMethods );
  tree.root = null;
  return tree;
};

var binarySearchTreeMethods = {

  insert: function (value, node) {
    var newNode = binaryTreeNode( value );

    // check if tree is empty
    if ( this.isEmpty() ) {
      this.root = newNode;
      return;
    }

    // initialize node
    if ( node === void 0 ) node = this.root;

    // compare value with node.value
    if ( value <= node.value ) {
      // check if left exists
      if ( node.left ) {
        this.insert( value, node.left );
      } else {
        node.left = newNode;
      }
    } else {
      if ( node.right ) {
        this.insert( value, node.right );
      } else {
        node.right = newNode;
      }
    }
  },

  remove: function (value, node) {
    var nextRightValue, nextLeftValue, minRight;

    if ( !this.isEmpty() ) {
      // initialize node
      if ( node === void 0 ) node = this.root;

      // compare the node's value with the value
      if ( value < node.value ) {
        // check if there is a left node
        if ( node.left ) {
          node.left = this.remove( value, node.left );
        }
      } else if ( value > node.value ) {
        // check if there is a right node
        if ( node.right ) {
          node.right = this.remove( value, node.right );
        }
      } else {
        // at this point, value === node.value
        // check if node is a leaf node
        if ( node.left === null && node.right === null ) {
          // edge case of single node in tree (i.e. root node)
          if ( this.getHeight() === 0 ) {
            this.root = null;
            return this.root;
          } else {
            node = null;
          }
        } else if ( node.left === null ) {
          node = node.right;
        } else if ( node.right === null ) {
          node = node.left;
        } else {
          // node has both left and right
          minRight   = this.findMinValue( node.right );
          node.value = minRight;
          node.right = this.remove( minRight, node.right );
        }
      }
      return node;
    }
  },

  contains: function (value, node) {
    if ( this.isEmpty() ) return false;
    // tree is not empty - initialize node
    if ( node === void 0 ) node = this.root;

    // check if node's value is the value
    if ( value === node.value ) return true;
    if ( value < node.value ) {
      // check if left node exists
      return node.left ? this.contains( value, node.left ) : false;
    } else {
      // check if right node exists
      return node.right ? this.contains( value, node.right ) : false;
    }
  },

  findMaxValue: function (node) {
    if ( !this.isEmpty() ) {
      if ( node === void 0 ) node = this.root;
      while ( node.right ) {
        node = node.right;
      }
      return node.value;
    }
  },

  findMinValue: function (node) {
    if ( !this.isEmpty() ) {
      if ( node === void 0 ) node = this.root;
      while ( node.left ) {
        node = node.left;
      }
      return node.value;
    }
  },

  getHeight: function (node) {
    if ( !this.isEmpty() ) {
      // initialize node
      if ( node === void 0 ) node = this.root;

      // base case
      if ( node.left  === null && node.right === null ) return 0;
      if ( node.left  === null ) return 1 + this.getHeight( node.right );
      if ( node.right === null ) return 1 + this.getHeight( node.left );
      return 1 + Math.max( this.getHeight( node.left ), this.getHeight( node.right ) );
    }
  },

  isEmpty: function () {
    return this.root === null;
  }

};

将值插入二叉搜索树工作正常:

var bst = binarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(20);
bst.insert(30);
bst.insert(22);
bst.insert(18);

每当我开始删除root值时,我遇到了一个问题:

bst.remove(10); // this works fine and the resulting bst tree is structurally correct
bst.remove(18); // this works fine and the resulting bst tree is structurally correct
bst.remove(20); // this works fine and the resulting bst tree is structurally correct
bst.remove(22); // this works fine and the resulting bst tree is structurally correct
bst.remove(30); // THIS IS WHERE THE ISSUE OCCURS

在删除30之前,树只有两个值:30作为根值,5作为root.left值.我希望删除30会给我一棵树,其中有5根作为根.但是,删除30对树没有任何作用; 它保持不变.

进一步的测试表明,如果我先删除5然后删除30,那么一切都正常:

bst.remove(10); // this works fine and the resulting bst tree is structurally correct
bst.remove(18); // this works fine and the resulting bst tree is structurally correct
bst.remove(20); // this works fine and the resulting bst tree is structurally correct
bst.remove(22); // this works fine and the resulting bst tree is structurally correct
bst.remove(5);  // Results in a tree with 30 as the root value
bst.remove(30); // Results in the empty tree where root === null

任何人都可以帮助我理解为什么删除30最初不起作用？

Answer 1

当找到的节点是根节点并且它是树中的唯一节点,并且如果节点同时具有左子节点和右子节点时,您的代码可以为此情况提供条件,则会覆盖其值.但是当要删除的节点是根并且它只有一个子节点时,代码中没有任何内容会覆盖this.root,并且您不会覆盖根的值,因此不会删除它并且树保持不变.

您可以通过更改此设置来解决此问题

if ( node === void 0 ) node = this.root;

// compare the node's value with the value
if ( value < node.value ) {

对此:

if ( node === void 0 ) {
    this.root = this.remove(value, this.root);
// compare the node's value with the value
} else if ( value < node.value ) {

修复后,您可以简化逻辑:

remove: function (value, node) {
    if (!this.isEmpty()) {
        // initialize node
        if (!node) {
            this.root = this.remove(value, this.root);
        } else if (value < node.value && node.left) {
            node.left = this.remove(value, node.left);
        } else if (value > node.value && node.right) {
            node.right = this.remove(value, node.right);
        } else if (value === node.value) {
            // check if node is a leaf node
            if (node.left && node.right) {
                // node has two children. change its value to the min
                // right value and remove the min right node
                node.value = this.findMinValue(node.right);
                node.right = this.remove(node.value, node.right);
            } else {
                // replace the node with whichever child it has
                node = node.left || node.right;
            }
        }
        return node;
    }
},

然后你可以通过将它分成两个方法来进一步简化它:

remove: function (value) {
    this.root = this._removeInner(value, this.root);
},

_removeInner: function (value, node) {
    if (node) {
        if (value < node.value) {
            node.left = this._removeInner(value, node.left);
        } else if (value > node.value) {
            node.right = this._removeInner(value, node.right);
        } else if (node.left && node.right) {
            node.value = this.findMinValue(node.right);
            node.right = this._removeInner(node.value, node.right);
        } else {
            node = node.left || node.right;
        }
    }
    return node;
},

演示

@wmock问我是如何解决这个问题的,所以我会详细说明一下.

我做的第一件事就是在调试器中执行代码,重点关注bst.remove(30)部件.我注意到30点是那个点上的根,它在remove()完成后仍然存在.这让我注意到代码永远不会修改特定情况下的根.

然后我看着如何的返回值this.remove()被分配给node.left和node.right,并与BST算法的一些回忆,认为这将是有意义的仿效,对于根也.这确实是答案.

有一些事情促使将该方法分为两种方法:

• 我注意到该方法具有相当多的特殊功能,仅与初始调用相关 bst.remove()
  • 检查 this.isEmpty()
  • 使用this.root该值node如果node为空
  • this.root树高为0时,在某些情况下重置为null

在每次通过中做这一切似乎很草率 remove()

• 我也反复发现自己想用来if (!node)检查我是否已到达树的边缘,但我不能,因为this.root当nodenull为空时,会使用特殊情况逻辑.

将方法拆分为两部分解决了上述所有问题.

请注意,在许多BST实现中,函数_removeInner()将是binaryTreeNode类型上的方法,并且树将仅与根节点交互.这消除了将节点从一个方法调用传递到下一个方法的需要:

在binarySearchTree:

remove: function (value) {
    this.root && this.root.remove(value);
},

在binaryTreeNode:

remove: function (value) {
    if (value < this.value) {
        this.left = this.left && this.left.remove(value);
    } else if (value > this.value) {
        this.right = this.right && this.right.remove(value);
    } else if (this.left && this.right) {
        this.value = this.right.findMinValue();
        this.right = this.right.remove(this.value);
    } else {
        return this.left || this.right;
    }
    return this;
},

findMinValue: function () {
    return this.left ? this.left.findMinValue() : this.value;
}

演示