红黑树 - return 所有大于 X 的值按排序顺序排列

Question

我的项目中确实需要这个功能。也就是说，我有一个红黑树，我需要编写一个函数来 return 排序顺序中所有高于 X 的值。

示例：

给定以下彩铃

https://upload.wikimedia.org/wikipedia/commons/thumb/6/66/Red-black_tree_example.svg/500px-Red-black_tree_example.svg.png

函数 greater(6) 应该 return [ 6, 8, 11, 13, 15, 17, 22, 25, 27]

函数 greater(11) 应该 return [13, 15, 17, 22, 25, 27]

有什么建议吗？鉴于我已经找到节点 X 的事实，递归是什么？

Answer 1

在树上进行中序遍历，当你发现一个大于给定值的值时，将其推入结果数组并return返回。

更新优化：

We don't have to check the left subtree of the current node if the value of the current node is < than the target boundary value. Only check the left subtree if its value is >= target boundary value.

这是使用 Javascript 代码的工作示例。

/**
 * Function to create a tree node with null left and right child
 * @param {Number} val
 * @return {Node} tree node
 * */
function Node(val) {
  this.value = val;
  this.left = null;
  this.right = null;
}
// Constructing the tree
const root = new Node(13);
root.left = new Node(8);
root.left.left = new Node(1);
root.left.left.right = new Node(6);
root.left.right = new Node(11);
root.right = new Node(17);
root.right.left = new Node(15);
root.right.right = new Node(25);
root.right.right.left = new Node(22);
root.right.right.right = new Node(27);

/**
 * In-order traversal of a  binary tree.
 * While processing the current node, we will check and push the value to result array
 * @param {Node} node
 * @param {Number} contraint value
 * @param {Number[]} result array
 * @return {Void}
 * */
function inorder(node, val, result) {
  if (node == null) return;
   /** 
   * We don't have to check the left subtree of the current node if the value 
   * of the current node is < than target boundary value. Only check left
   * subtree if its value is >= target boundary value.
   * */
  if(node.value >= val) {
      inorder(node.left, val, result);
  }
  
  if (node.value > val) {
    result.push(node.value);
  }
  inorder(node.right, val, result);
}

/**
 * @param {Node} root
 * @param {Number} value
 * @return {Number[]} result
 * */
function getValuesAfter(root, value) {
  const result = new Array();
  inorder(root, value, result);
  return result;
}

console.log("Sorted values after 6:");
const result6 = getValuesAfter(root, 6);
console.log(result6.join(', '));

console.log("Sorted values after 11:");
const result11 = getValuesAfter(root, 11);
console.log(result11.join(', '));



console.log("Sorted values after 22:");
const result22 = getValuesAfter(root, 22);
console.log(result22.join(', '));

红黑树 - return 所有大于 X 的值按排序顺序排列

Red Black Tree - return all the values greater than X in sorted order

sorting

algorithm

red-black-tree

更新优化：