Category Archives: Computer Theory

Tips for traversing a tree with stacks

 

Here are the tips of my solution:

  • You always push the root to the stack first
  • The most difficult part is: when you see a node on the top of element, should you go on to push its children, or pop it to print it? 
    • For pre-order traversal, you can pop it then push their children.  
    • For in-order traversal, you need to check whether its left child has been popped yet.  If yes, pop it; else, push its left child. 
      • You can add a flag to the node when it is pushed to stack with initial value equals to False.  
      • Enquiry this flag before deciding whether to pop current node.  If True, do a pop; If False, set this flag as True before pushing its left child. 
      • You should set the flag to True even if its left child is Null
    • For post-order traversal, you need to check whether both its children have been popped yet. This time you need two flags. 

二叉查找树与平衡二叉树

内容编译自网络

Binary Search Tree

什么情况下会出现O(n) ? 如果树的根结点没选好,一棵树变成一个列表:

平衡二叉查找树 –  可以自动旋转

参考:

http://en.wikipedia.org/wiki/Binary_search_tree
http://www.cnblogs.com/huangxincheng/archive/2012/07/21/2602375.html
http://www.cnblogs.com/huangxincheng/archive/2012/07/22/2603956.html

三种i/o模式:异步模式与阻塞模式的组合

阻塞且同步: read()方法要等到读到数据了才返回,如果没数据就会一直等

非阻塞且同步: read()方法如果发现当前没数据,就会返回; 调用者可以去做别的事情。然后过段时间再读(轮询)

非阻塞且异步:read()方法如果发现当前没数据,会返回; 调用者可以去做别的事情,也不用再轮询,等操作系统把数据读好了,会通过回调方式把数据交给调用者。

阻塞并异步: 没有这样的组合,这种组合也没有意义

归纳一下:

  阻塞/非阻塞:读不到数据方法就不退出,就是阻塞

  同步/异步:   读不到数据需要主动重试,就是同步; 如果数据好了惊醒你,就是异步。

可以看出,”非阻塞且异步“是性能最好的模式,它避免无谓的等待,节省线程数;避免无效读,提高线程的工作效能。

参考材料:
http://www.artima.com/articles/io_design_patterns.html