10.17 Implement (an API for) Locking in a Binary Tree

#1

First off, thank you for the book, its organization and set of problems! This is my first post to the forum and I can’t thank you guys enough.

Here is the problem 10.17 as seen on my Google Play Version 1.6.1 of EPI (Java):

Pasted image691×162 26.4 KB

The given solution however does not seem to provide a good API. Here is how a (single threaded!) caller is supposed to call it:

if (!node.isLocked()) {
  if (node.lock()) {
    // only now is it locked, which means isLocked call was not useful
  }
}

It’s a disaster if the caller forgets to do if (node.lock()) and simply does node.lock() ignoring the return value (thinking that the check for isLocked() already says that it is not locked. So, the expectation on the caller’s part is that the call to lock() would succeed in locking the node.

Wouldn’t it be better if we had only lock() and unlock() methods to avoid this problem?

Thanks!

0 Likes
#2

Hey @Curious.George,

First off, thanks for your kind words on EPI. It is always good to receive compliment from readers.

About your suggestion, I think it is fine since lock() will return false if it cannot be locked. I agree with your point that isLock() api seems redundant but here we are solving a problem that we did not define the usage of this binary tree such that I feel there is no need to remove that isLock() api here.

Again, thanks for your support, and let us know if you have any other questions.

0 Likes
#3

I have one question. The solution to this problem mentions keeping count of child locked nodes. However it seems to me it is possible to have only one boolean flag for a node indicating whether any given node in the subtree of this node (including this node itself) is locked. Then isLocked() would just check if this flag is true for this node and false for its children. For lock() we can check this flag for this node (return false if its sent) and call isLocked() on ancestors to check if they are locked first. Then locking is trivial. For unlock(), we set this flag to false for this node, then for each ancestor, we set it to false only if it is false for the other child of that ancestor’s subtree (meaning no node is locked in the other child’s subtree). The running time should be the same. Am i missing something here?

(sorry for the spoiler, not sure if i was allowed to post solution here)

Thanks,
Yev

0 Likes
#4

It seems like its ok to post the code here, here is Java code:

    public static class BinaryTree {
		public Object data;
		public BinaryTree left, right, parent;
		public boolean locked;
					
		public boolean isLocked()
		{
			return locked && (left == null || !left.locked) && (right == null || !right.locked);
		}
		
		public boolean lock()
		{
			if (locked) //if any node in this subtree is locked
				return false;
			for(BinaryTree n = parent; n != null; n = n.parent) //all ancestors
				if (n.isLocked())
					return false;
				
			//put lock on this and all ancestor subtrees
			for(BinaryTree n = this; n != null; n = n.parent)
				n.locked = true;
			return true;
		}
		
		public void unlock()
		{
			if (!isLocked())
				return;
			locked = false;
			for(BinaryTree n = this; n.parent != null; n = n.parent)
				if ((n.parent.left == this && !n.parent.right.locked) || (n.parent.right == this && !n.parent.left.locked))
					n.parent.locked = false;
		}
	}

}

0 Likes
#5

I think the idea works. One small bug in your code is in unlock() where you need to check the validness of n.parent.right before accessing n.parent.right.locked (similar thing for n.parent.left). Other that, I think this works because the original idea of using a counter is for the extension of general tree. However, for binary tree, we definitely can simplify this to a boolean variable with additional check.

Thanks for providing this idea!

0 Likes
#6

Yeah, thanks for pointing this out. Need null check for n.parent.right and n.parent.left.

Regards,
Yev

0 Likes