Struct_chapter3_Tree

3.1 tree and the expression of tree

• concept of tree
  an excellent struct to expresses hierarchical relationship(层次关系)
• more efficienct

---

• Searching
  
• 0x01 static searching
  
  notice : 哨兵(tag)
  two probable status to exit :
  1.find K in list(return index)
  2.no K except the station of tag(return 0)
  3.时间复杂度o(n) [n/2]
  
• 0x02 binary search(二分查找)
• 不可采用chain list [one-way]
  
  status 1 find correct answer
  
  
  
  status 2 no correct answer
  
  realization and enlightenment
  
  

thought bubble : optimize

黄金分割查找？
在二分查找中，我们是取mid等于left和right的中间值，即用等分的方法进行查找。
那为什么一定要等分呐？能不能进行“黄金分割”？也就是mid=left+0.618(right-left),当然mid要取整数。如果这样查找，时间复杂性是多少？也许你还可以编程做个试验，比较一下二分法和“黄金分割”法的执行效率。

• dynamic searching