Labels

_fuxi (75) _IV (146) _misc (5) {610610 (30) algo (1) automatedTrading (8) banking/economy (3) book (14) c++misc (125) c++real (15) c++STL/java_container (7) cppTemplate (1) db (13) DB_tuning (4) deepUnder (1) dotnet (69) eTip (17) excelVBA (12) finance+sys (34) financeMisc (24) financeRisk (2) financeTechMisc (4) financeVol (21) finmath (17) fixedIncome (25) forex (16) IDE (24) invest (1) java (43) latency (4) LinearAlgebra (3) math (30) matlab (24) memoryMgmt (11) metaPrograming (2) MOM (15) msfm (1) murex (4) nofx (11) nosql (3) OO_Design (1) original_content (4) scriptUnixAutosys (19) SOA (7) socket/stream (15) sticky (1) subquery+join (2) swing (32) sybase (6) tech_orphan (12) tech+fin_career (30) telco (11) thread (21) timeSaver (13) tune (10) US_imm (2) US_misc (2) windoz (20) z_algo+dataStructure (4) z_arch (2) z_c#GUI (30) z_career (10) z_career]US^Asia (2) z_careerBig20 (1) z_careerFinanceTech (11) z_FIX (6) z_forex (31) z_hib (2) z_ikm (7) z_inMemDB (3) z_j2ee (10) z_oq (14) z_php (1) z_py (26) z_quant (4) z_skillist (3) z_spr (5)

Friday, June 22, 2007

binary search tree

defining property: any node to my left is smaller or equal. left child <= parent AND right-child >= parent. Both children is allowed to be equal to parent -- binary search tree is completely unbiased.

The defining property defined visually: For each node, draw a vertical line (long shadow) through the tree.
* Left descendants' v-lines are on or inside my v-line.
* Right descendants' v-lines are on or outside my v-line.

When nodes move up or down the three, their shadows shift. I think this may help us visualize a BST successor, deletion and insertion.

the same group of items can build 2 different bs-trees, with different tree heights. How? The same entries could arrive out of sequence, just like IP packets.

The deeper the tree, the more iterations for a tree walk, the slower the sort.
Worst case bst has a tree height equal to input size, with one branch at each node?