40 " |
40 " |
41 Loosely based on the Public Domain BinaryTreeNode class from Steve Chepurny. |
41 Loosely based on the Public Domain BinaryTreeNode class from Steve Chepurny. |
42 |
42 |
43 WARNING: |
43 WARNING: |
44 This tree does not reorganize itself. |
44 This tree does not reorganize itself. |
45 Thus, its performance might degenerate to that of a linked list (see performance). |
45 Thus, its performance might degenerate to that of a linked list (see performance) when elements |
46 The performance is OK, if elements are added in random order and the tree is therefore balanced. |
46 are added in 'already sorted' or reverse order. |
|
47 The performance is OK, if elements are added in random order and the tree is therefore more or less |
|
48 balanced. |
47 The worst case is to add elements in order, reverseOrder or zig-zag order. |
49 The worst case is to add elements in order, reverseOrder or zig-zag order. |
48 Use instances of my subclasses, which balance the tree if in doubt. |
50 Use instances of my subclasses, which balance the tree if in doubt. |
49 |
51 |
50 EXTRA WARNING: |
52 EXTRA WARNING: |
51 the inherited storeString will generate the elements in sorted order, |
53 the inherited storeString will generate the elements in sorted order, |
52 which generates exactly the generated case when read-back. |
54 which generates exactly the generated worst case when read-back. |
53 If you use this class and need textual persistency, you should consider rewriting |
55 If you use this class and need textual persistency, you should consider rewriting |
54 the storeOn: method, to enumerate elements in a binary segmentation fashion. |
56 the storeOn: method, to enumerate elements in a binary segmentation fashion. |
55 Otherwise, please use one of the balanced trees instead, |
57 Otherwise, please use one of the self-balancing trees instead, |
56 for example AATree or BTree. |
58 for example AATree or BTree. |
57 |
59 |
58 Changes: |
60 Changes: |
59 Changed to be Collection-protocol compatible. |
61 Changed to be Collection-protocol compatible. |
60 Slight speedup in insert-code. |
62 Slight speedup in insert-code. |