Two BST walkthroughs in order

Question

These days, I tried to implement the function that my professor asked us to make as a challenge, but I can’t think about the possibility of doing this, so I’m here to find out if anyone can shed light on this.

It will just be an algorithm for this, but I actually program it in C ++ using a BSTree programmed in accordance with the basic specification (insert, delete, member operations).

The problem is this:

Assuming each tree node contains a number in an absolute number, and we have two different BSTs: one for storing negative numbers, and the other for storing positive numbers. We can call them negBST and posBST. For example, if you enter numbers -2 2 5 8 -4 -5 -3 -6, these will be our two trees:

2                        2
 \                        \
  4                        5
 / \                        \
3   5                        8
     \
      6
Negative BST               Positive BST

, , :

2 -2 -3 -4 5 -5 -6 8 

: - (, , , ..)...?

EDIT:      , .

Answer 1

, n MAX_NUMBER , n . , ( , ).

. , . .

: DFS. , . , . ( ) DFS . . , , ..

Javascript/C-like:

// let assume a DFS and its status is represented by an object
// dfs.next() returns the next number and advances the search
// dfs.peekNext() only returns the next number

var dfsPos = initDFS(posBST);
var dfsNeg = initDFS(negBST);

while (!dfsPos.hasFinished() || !dfsNeg.hasFinished()) {
    if (dfsPos.hasFinished())
        print('-' +dfsNeg.next());
    else if (dfsNeg.hasFinisehd())
        print(dfsPos.next());
    else if (dfsPos.peekNext() < dfsNeg.peekNext()) 
        print(dfsPos.next());
    else
        print('-' +dfsNeg.next());
}

Answer 2

, negBST posBST .

, BST: s /, BST, commonBST, - . , BST, , :

• (: -2 2 5 8 -4 -5 -3 -6) BST commonBST ; KEY = abs(number), KEY, KEY.sign. KEY :

  • nil ( )
  • (KEY, KEY.keySign=-1 -)
  • (KEY, KEY.keySign=+1 +)
  • (KEY, , KEY.keySign=0)

• ( , ), negBST posBST BST, .

negBST posBST , commonBST - +, - .

, commonBST ( ):

For key C:
    C*: C contains both +C and -C (keySign = 0)
    C : C contains only one of +C and -C (get sign from keySign)

Example binary tree for numbers [-2, 2, 5, 8, -4, -5, -3, -6]:

    2*
     \
     5*
   /    \
  4      8
 /      /
3      6

// adapted from "regular" BST in Swift from: 
// http://waynewbishop.com/swift/binary-search-trees/

//generic binary search tree
public class AVLTree {
    var key: Int?
    var keySign: Int? // -1 or 1 for unique entries, 0 if both
    var left: AVLTree?
    var right: AVLTree?

    init() { }

    //add item based on its value
    func addNode(key: Int) {

        //check for the head node
        if (self.key == nil) {
            self.key = abs(key)
            self.keySign = abs(key)/key
            return
        }

        // check for duplicate key
        if (abs(key) == self.key) {
            self.keySign = 0
        }

        //check the left side of the tree
        else if (abs(key) < self.key) {
            if (self.left != nil) {
                left!.addNode(key)
            }
            else {
                //create a new left node
                let leftChild : AVLTree = AVLTree()
                leftChild.key = abs(key)
                leftChild.keySign = abs(key)/key
                self.left = leftChild
            }
        }

        //check the right side of the tree
        else if (abs(key) > self.key) {
            if (self.right != nil) {
                right!.addNode(key)
            }
            else {
                //create a new right node
                let rightChild : AVLTree = AVLTree()
                rightChild.key = abs(key)
                rightChild.keySign = abs(key)/key
                self.right = rightChild
            }
        }
    }
}

let numberList : Array<Int> = [-2, 2, 5, 8, -4, -5, -3, -6]

//create a new BST instance
var root = AVLTree()

//sort each item in the list
for number in numberList {
    root.addNode(number)
}

, .

CommonBST BST, keySign .

• keySign=1, print(key).
• keySign=-1, print(-key).
• keySign=0, print(-key) print(key) ( ).

, BST, O (log n) .