answer in pseudo code Give a data structure to the following, in case values are

Question

answer in pseudo code

Give a data structure to the following, in case values are not pairwise disjoint. Each element has a second key. The second key of x is denoted sk(x). The sk(x) values of items that have value x, are pairwise disjoint. Give a data structure that supports: that supports: (a) Insert(x, S) (b) Delete(x, S) (c) Print(x, S) Here x is the key that may not be unique., The print operation asks to print all the pairs whose first value is x (it could be that the first value is the same for many items).

Explanation / Answer

//pseudo code

def findval (node,lookfor):

    if node is null:

        return null

    if node.val is equal to lookfor:

        return node

    if node.val is less than lookfor

        return findval (node.right,lookfor)

    return findval (node.left,lookfor)

def findval (node,lookfor):

    while node is not null:

BinaryTree.prototype.getRoot = function() {...}

//pseudo code for insertion

BST-Insert(x, z, k)
1: if x = nil then return “Error”
2: y x
3: while true do {
4: if key[y] < k
5: then z left[y]
6: else z right[y]
7: if z = nil break
8: }
9: if key[y] > k then left[y] z
10: else right[p[y]] z

//pseudo code for Print

BST-Successor(x)
1: if right[x] 6= nil then
2: { y right[x]
3: while left[y] 6= nil do y left[y]
4: return (y) }
5: else
6: { y x
7: while right[p[x]] = x do y p[x]
8: if p[x] 6= nil then return (p[x])
9: else return (“NO SUCCESSOR”) }

//pseudo code for Deletion

BST-Delete(T, z)
1: if left[z] = nil or right[z] = nil
2: then y z
3: else y BST-Successor(z)
4: y is the node that’s actually removed.
5: Here y does not have two children.
6: if left[y] 6= nil
7: then x left[y]
8: else x right[y]
9: x is the node that’s moving to y’s position.
10: if x 6= nil then p[x] p[y]
11: p[x] is reset If x isn’t NIL.
12: Resetting is unnecessary if x is NIL.

13: if p[y] = nil then root[T] x
14: If y is the root, then x becomes the root.
15: Otherwise, do the following.
16: else if y = left[p[y]]
17: then left[p[y]] x
18: If y is the left child of its parent, then
19: Set the parent’s left child to x.
20: else right[p[y]] x
21: If y is the right child of its parent, then
22: Set the parent’s right child to x.
23: if y 6= z then
24: { key[z] key[y]
25: Move other data from y to z }
27: return (y)

BinaryTree.prototype.setRoot = function(root) {...

BinaryTree.prototype.getCount = function() {...}

BinaryTree.prototype.build = function(array) {...}

BinaryTree.prototype.swapNodes = function(node1, node2) {...}

BinaryTree.prototype.getNode = function(index) {...}

BinaryTree.prototype.getIndex = function(node) {...}

        if node.val is equal to lookfor:

            break

        if node.val is less than lookfor:

            node = node.right

        else:

            node = node.left

    return node

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.