Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* this algorithm looks for the common elements in both the given BST and the specified range.
- pre-condition: the begining and the end elements of the range.
- post-condition: returns the number of common elements. */
- Algortihm countRange(int firstKey, int secondKey)
- return rootNode(tree.root, firstKey, secondKey);
- END
- /*this algorithm keeps checking the root node to make sure it is within the specified given range and if not it keeps going down level by level till it
- gets to a node that is within the given range
- pre-condition: the given binarysearchtree has nodes with integer values.
- The firstKey is the begining of the given range and the second key is the end of the given range
- post-condition: the cardinality of the intersection of the range and the binary tree is returned. */
- Algortihm countRangeHelper(Node root, int firstKey, int secondKey)
- if (root = null)
- return null;
- if (root.value < firstKey)
- rootNode(root.right, firstKey, secondKey);
- end IF
- else if(root.value > secondKey)
- rootNode(root.left, firstKey, secondKey);
- end ELSE IF
- else return (left(root, firstKey) + right(root, secondKey) + 1);
- END
- /* this algorithm computes the number of right elements in the range, in the left sub-tree.
- pre-condition: a node in the tree and the begining of the given range are passed through.
- post-condition: number of right elements in the range, in the left sub-tree is returned. */
- Algortihm left(Node node, int firstKey)
- if (node.value > firstKey)
- return (node.right.size + 1 + left(node.left, firstKey));
- end IF
- else if (node.value < firstKey)
- return (left(node.right, firstKey));
- end ELSE IF
- else
- return (node.right.size + 1);
- end ELSE
- END
- /* this algorithm computes the number of right elements in the range, in the right sub-tree.
- pre-condition: a node in the tree and the end of the given range are passed through.
- post-condition: number of right elements in the range, in the right sub-tree is returned. */
- Algortihm right(Node node, int secondKey)
- if (node.value > secondKey)
- return (right(left.size));
- end IF
- else if (node.value < secondKey)
- return (node.left.size + 1 + right(node.right, secondKey);
- end ELSE IF
- else
- return (node.left.size + 1);
- end ELSE
- END
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement