Linenは移転しました。新しいURLはhttp://comelun.com/です。
ココのログはしばらくそのままにしておきます。
並び順： 階層 時系列
0
+16		(・_・)しらちゃ[2.1 01:03]
!m アルゴリズムメモ☆
1
+1		(・_・)しらちゃ[2.1 01:05]
☆
・ツリーは，ヨコに(同一の親の子が)M，タテ(深さ)にNが最大とします
・全てのノードは
　　・level値 : ゼロの階層を0として，何段目なのかを数える値
　　・id値 : 同じ親を持つ子の中で，何番目の子なのかの，一意値
　　・left値 : ちょっと工夫された，ツリー所属性検索用番号(自然数)
を持ちます
8
(・_・)しらちゃ[2.1 01:17]>>1
id値は解りづらいかもしれませんが，「高々m」の値になります．☆
2
+3		(・_・)しらちゃ[2.1 01:08]
☆
・ノードの挿入
ある親ノードに子ノードを追加する場合，
子ノードのレベルが n だとするならば(即ち親ノードのレベル「n' + 1」)
親ノードleft + 子ノードid * (M ** (N-n))
にノードを追加します．
※１．特に，ゼロの追加は，親ノードleftを0として，
0 + id * (M ** (N-n))
となります．
※２．「**」は冪乗を表します．
9
(・_・)しらちゃ[2.1 01:20]>>2
☆
※１’．訂正
特に，ゼロの追加は，親ノードleftを0，階層nを0として，
0 + id * (M ** (N-n)) = id * (M**N)
となります．
11
(・_・)しらちゃ[2.1 04:14]>>2
補足１．ここでいう「ノードの追加」っていうのは，そういうLeftの値を書き込むということです．☆
14
(・_・)しらちゃ[2.1 12:58]>>2
※補足２．さらにゼロのidは0なので，必ず 0 + 0*(M**N) = 0となることまで言えたりする．☆
3
(・_・)しらちゃ[2.1 01:09]
☆
・単一ノード検索
level, id, leftの三つ組で全てのノードが一意に決定可能です(証明済み)
4
(・_・)しらちゃ[2.1 01:11]
☆
・部分ツリー検索
ある親の元にある子の連鎖としてのツリー(部分ツリー)は，
nを親のlevelとすると
　levelがn以上　かつ　(親のleft)以上　かつ　(親のleft + M**(N-n))よりも少ない
ノードの集合です
5
(・_・)しらちゃ[2.1 01:14]
この方法なら，32bitの自然数をleftに使えば，N=10, M=9とか，N=9, M=11とかくらいのサイズのツリーが実現できます．☆
6
(・_・)しらちゃ[2.1 01:14]
具体的には，自然数のインデクスをM**Nだけ消費します．☆
7
(・_・)しらちゃ[2.1 01:14]
left値ですね．☆
10
(・_・)しらちゃ[2.1 01:21]
64bitならN=14, M=23あたりが順当かな？使い方に合わせて色々選択肢はあると想うけど．☆
12
+3		(・_・)"蒼き稲妻"青ペン先生[2.1 07:18]
M**Nアルゴリズム。雰囲気だけ理解。なにか面白い用途がありそう ##SQL☆
13
+2		(^-^)しらちゃ[2.1 12:57]>>12
はい．今回は普通にLinenに使うのだっていけるはず．☆
15
+1		(・_・)"蒼き稲妻"青ペン先生[2.1 16:47]>>13
Linenのユーザの使い方を見ると、ひたすら横に伸ばすときと縦に伸ばす時があるから、UIでその辺をうまく絞ってやるといいような気がする☆
16
(・_・)しらちゃ[2.1 16:49]>>15
☆
縦と横の片方に集中すると，確かに，このアルゴリズム，すっ飛びそうですね．
ここまでに私が提案したのは，静的にツリー構造を決定する物なので，動的にすることを考えないと，そういうことには対処できそうにないです．．．