二分探索木で例えば1〜10の値を順番に追加したら偏った木になると思うのですが、バランスの良い木にする

二分探索木で例えば1〜10の値を順番に追加したら偏った木になると思うのですが、バランスの良い木にするためにはどのように値を追加すれば良いのでしょうか？？

No.5 回答者： cametan_42 回答日時： 2021/07/24 22:20

さて、#3だと「一旦1〜10を順番に追加して」偏った木を一気にバランスの良い木に変換する、って手法を紹介しましたが。

そうじゃなくって、順次値を追加する度に木を更新する、って手段だとどうなるか。その一つを紹介しようと思います。

またもやWikipediaからアスキーアートならぬAA木と言うアルゴリズムを。

AA木:
https://ja.wikipedia.org/wiki/AA%E6%9C%A8

これは

> 順序のあるデータを効率的に格納し

と言うので、例によって「1〜10の値を順番に追加」していくんだけど、リアルタイムに木を弄ってバランスの良い木に変換する手法の模様です。
ただし、一般的に平衡二分探索木の場合、

> 平衡二分探索木を常に最小の高さに保つのは高くつくので、いつも正確に平衡している必要はない。

ので、このアルゴリズムを適用しても、完全平衡木に毎回必ずしもなる、ってワケではない様です。

ではまずはノードの設計から。
詳しい内情はWikipediaに譲りますが、この場合のノードには通常ノードに求められる情報に加えて、「レベル」と言う情報があります。木が末葉から数えて何段目に存在するのか、と言う情報ですね。
また、ここではWikipediaに書かれてる「削除」と言うメソッドは実装していません。今回の題意から言うと不必要だから、ですね。
ただ、Wikipediaには疑似コードが載ってますし、疑似コードをどうやってJavaのコードとして書き換えるのか、と言うのは一回自分でやってみれば良い、と思ってるんで、サンプル程度としてそれ以外を提示しておけば自分で実装可能な範疇だ、と思っています。

// TreeNode.java

public class TreeNode {
　int value;
　int level;
　TreeNode left;
　TreeNode right;
　TreeNode (int value, int level, TreeNode left, TreeNode right) {
　　this.value = value;
　　this.level = level;
　　this.left = left;
　　this.right = right;
　}
　static TreeNode skew(TreeNode T) {
　　if (T == null) {
　　　return null;
　　} else if (T.left == null) {
　　　return T;
　　} else if (T.left.level == T.level) {
　　　// 水平左リンクの木を入れ替える。
　　　TreeNode L = T.left;
　　　T.left = L.right;
　　　L.right = T;
　　　return L;
　　} else {
　　　return T;
　　}
　}
　static TreeNode split(TreeNode T) {
　　if (T == null) {
　　　return null;
　　} else if ((T.right == null) || (T.right.right == null)) {
　　　return T;
　　} else if (T.level == T.right.right.level) {
　　　// 水平右リンクが2つある場合。真ん中を持ち上げて、それを返す。
　　　TreeNode R = T.right;
　　　T.right = R.left;
　　　R.left = T;
　　　R.level += 1;
　　　return R;
　　} else {
　　　return T;
　　}
　}
　public TreeNode insert(int X, TreeNode T) {
　　// まず、通常の2分木の挿入操作を行う。新たなノードが作成されたか
　　// 部分木の根が変わったバイ、再帰呼出しの結果を正しい子ノードに設定する。
　　if (T == null) {
　　　// X に対応する新たな葉ノードを生成
　　　return new TreeNode(X, 1, null, null);
　　} else if (X < T.value) {
　　　T.left = insert(X, T.left);
　　} else if (X > T.value) {
　　　T.right = insert(X, T.right);
　　}
　　// X == T.value の場合がない点に注意。その場合、挿入は行われない。
　　// 場合によっては、違う動作が望ましいこともある。

　　// skew を行い、次いで split を行う。実際に回転をするかどうかは
　　// 上掲のようにこれら手続き内で判断する。

　　return split(skew(T));
　}
　// ノードの出力用メソッド
　public void print() {
　　print("", this, false);
　}
　public void print(String prefix, TreeNode n, boolean isLeft) {
　　if (n != null) {
　　　System.out.println(prefix + (isLeft ? "|-- ": "\\-- ") + n.value);
　　　print(prefix + (isLeft ? "| " : " "), n.left, true);
　　　print(prefix + (isLeft ? "| " : " "), n.right, false);
　　}
　}
}
// ここまで

次にMain.javaを書きます。こっちは短い。

// Main.java

public class Main {
　public static void main(String[] args) {
　　int DUMMY = 0;
　　int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
　　TreeNode tree = new TreeNode(DUMMY, 0, null, null);
　　for (int val: array) {
　　　tree.insert(val, tree);
　　　tree.print();
　　}
　}
}
// ここまで

コンパイルして実行してみれば、arrayで定義してるソート済みのデータが先頭から取り込まれてどう「回転」して平衡二分木を作っていくのか、その流れが分かると思います。

\-- 0
　　\-- 1

↓

\-- 0
　　\-- 1
　　　　\-- 2

↓

\-- 0
　　\-- 2
　　　　|-- 1
　　　　\-- 3

↓

\-- 0
　　\-- 2
　　　　|-- 1
　　　　\-- 3
　　　　　　\-- 4

↓

\-- 0
　　\-- 2
　　　　|-- 1
　　　　\-- 4
　　　　　　|-- 3
　　　　　　\-- 5

↓

\-- 0
　　\-- 2
　　　　|-- 1
　　　　\-- 4
　　　　　　|-- 3
　　　　　　\-- 5
　　　　　　　　\-- 6

↓

\-- 0
　　\-- 4
　　　　|-- 2
　　　　|　 |-- 1
　　　　|　 \-- 3
　　　　\-- 6
　　　　　　|-- 5
　　　　　　\-- 7

↓

\-- 0
　　\-- 4
　　　　|-- 2
　　　　|　 |-- 1
　　　　|　 \-- 3
　　　　\-- 6
　　　　　　|-- 5
　　　　　　\-- 7
　　　　　　　　\-- 8

↓

\-- 0
　　\-- 4
　　　　|-- 2
　　　　|　 |-- 1
　　　　|　 \-- 3
　　　　\-- 6
　　　　　　|-- 5
　　　　　　\-- 8
　　　　　　　　|-- 7
　　　　　　　　\-- 9

↓

\-- 0
　　\-- 4
　　　　|-- 2
　　　　|　 |-- 1
　　　　|　 \-- 3
　　　　\-- 6
　　　　　　|-- 5
　　　　　　\-- 8
　　　　　　　　|-- 7
　　　　　　　　\-- 9
　　　　　　　　　　\-- 10

まぁ、ダミーのルート0が残ってますが、レベル0は操作の影響を受けないので、事実上4をルートとした上のような平衡木(ただし完全ではない)が生成されて行くのが分かります。

No.4 回答者： Tacosan 回答日時： 2021/07/23 00:37

「バランスの良い木になる」ように追加すればいい.

あるいは平衡二分木.

No.3 回答者： cametan_42 回答日時： 2021/07/23 00:11

ああクソ、メンドクセェな、Javaは。

それでも最近慣れてきた、とか慢心してたんだけど、やっぱJavaは手こずります。

まず、ノードの設計から。

// TreeNode.java

public class TreeNode {
　int data;
　TreeNode left;
　TreeNode right;
　TreeNode(int data, TreeNode left, TreeNode right) {
　　this.data = data;
　　this.left = left;
　　this.right = right;
　}
　// 与えられた配列をそのまま基本に沿って二分木化する
　public TreeNode insert(int[] arr, TreeNode root, int i) {
　　if (i < arr.length) {
　　　TreeNode temp = new TreeNode(arr[i], null, null);
　　　root = temp;
　　　if (root.data > arr[i]) {
　　　　root.left = insert(arr, root.left, i + 1);
　　　} else {
　　　　root.right = insert(arr, root.right, i + 1);
　　　}
　　}
　　return root;
　}
　// ノードの出力用関数
　public void print() {
　　print("", this, false);
　}
　public void print(String prefix, TreeNode n, boolean isLeft) {
　　if (n != null) {
　　　System.out.println(prefix + (isLeft ? "|-- ": "\\-- ") + n.data);
　　　print(prefix + (isLeft ? "| " : " "), n.left, true);
　　　print(prefix + (isLeft ? "| " : " "), n.right, false);
　　}
　}
}

// ここまで

で、Main.javaファイルを作る。

// Main.java

public class Main{
　public static void main(String[] args) {
　　int DUMMY = 0;
　　TreeNode tree = new TreeNode(DUMMY, null, null);
　　int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
　　tree = tree.insert(arr, tree, 0);

　　tree.print();
　　int nodeCount = getNodeCount(tree);
　　tree = balanceVine(tree, nodeCount);
　　tree.print();

　}
　static TreeNode leftRotate(TreeNode n) {
　　if (n.right != null) {
　　　TreeNode rightChild = n.right;
　　　n.right = rightChild.right;
　　　rightChild.right = rightChild.left;
　　　rightChild.left = n.left;
　　　n.left = rightChild;

　　　int temp = n.data;
　　　n.data = rightChild.data;
　　　rightChild.data = temp;
　　}
　　return n;
　}
　static int getNodeCount(TreeNode root) {
　　if (root == null) {
　　　return 0;
　　}
　　int i = 1;
　　while (root.right != null) {
　　　root = root.right;
　　　i++;
　　}
　　return i;
　}
　public static int log2(int x) {
　　return (int) (Math.log(x) / Math.log(2));
　}
　static TreeNode balanceVine(TreeNode root, int nodeCount) {
　　int times = log2(nodeCount);
　　TreeNode newRoot = root;
　　for (int i = 0; i < times; i++) {
　　　newRoot = leftRotate(newRoot);
　　　root = newRoot.right;
　　　for (int j = 0; j < nodeCount / 2 - 1; j++) {
　　　　root = leftRotate(root);
　　　　root = root.right;
　　　}
　　　nodeCount >>= 1;
　　}
　　return newRoot;
　}
}

// ここまで

WikipediaのDSWアルゴリズムよりマシなアルゴリズム紹介がねぇか、って国内サイト探したんですが、無いカンジだったんで、海外サイトを調べてなんとかでっち上げてみました。
要するに配列が、例えば

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

とあったとして、ノードのデータに最初の値をセット。次に来る値がノードのデータより小さかったら左に、大きかったら右にデータをセットしつつ新しくノードを連結していくのが二分木作成の基本戦略なんですが。
提示の問題のように、ソート済みの配列を対象とすると、先に見たように蔦(あるいは背骨、って言い方もするみたいですが・笑)になってしまう。
こういう状態ですね。

\-- 1
　\-- 2
　　\-- 3
　　　\-- 4
　　　　\-- 5
　　　　　\-- 6
　　　　　　\-- 7
　　　　　　　\-- 8
　　　　　　　　\-- 9
　　　　　　　　　\-- 10

この状態の二分木に定義したbalanceVineを適用すると、次のような二分木に変換されます。

\-- 8
　|-- 4
　| 　|-- 2
　| 　| 　|-- 1
　| 　| 　\-- 3
　| 　\-- 6
　| 　　　|-- 5
　|　　　\-- 7
　\-- 10
　　　|-- 9

8がルート、と前の結果と違ってますね。
前は5段だったけど、今回は4段。こっちの方が「修正論文」に従ってて、完全な平衡木になってんじゃないのかな。

とまぁ、参考までに。

No.2 回答者： cametan_42 回答日時： 2021/07/22 15:36

これ、Javaで書くのメンドくせぇなぁ・・・・・・。

基本リファレンスだけにしとくか。

> 二分探索木で例えば1〜10の値を順番に追加したら偏った木になると思う

はい。
正攻法でそのまま二分木を作ろうとすると、次のような構造になると思うんですよね。

'(1 () (2 () (3 () (4 () (5 () (6 () (7 () (8 () (9 () 10)))))))))

全部右によって一本になっている。
この状態の(一本になってる)二分木を特に「蔦」と呼ぶらしい。英語だとvineですか。
んで、こいつをどうやってマトモなbinary-treeに変換するのか・・・・・・。

結論から言うと、Wikipediaに解決策が載ってました。その名もDSWアルゴリズム、です。

DSWアルゴリズム:
https://ja.wikipedia.org/wiki/DSW%E3%82%A2%E3%83 …

上のページにDSWアルゴリズムが載ってて、基本的に3つの関数(Javaだとメソッドか)を書けばバランスの良い木になるらしい。
そこで紹介されている3つは

・tree-to-vine ・・・・・・ バランスの悪い木を蔦へ変換する
・vine-to-tree ・・・・・・蔦をバランスの良い木へ変換する
・compress・・・・・・vine-to-treeの補助

なんですが、ここでの与題は、「既に蔦状態の木を」変換するのが目的なんで、単純にvine-to-treeとcompressの2つを実装すれば、そのまま解となる、って事ですね。
Pythonで試してみたら上手く行ったんで多分上手く行くんじゃないでしょうか。

>>> tree
[1, [], [2, [], [3, [], [4, [], [5, [], [6, [], [7, [], [8, [], [9, [], [10, [], []]]]]]]]]]]
>>> pseudo_node
[False, [], [1, [], [2, [], [3, [], [4, [], [5, [], [6, [], [7, [], [8, [], [9, [], [10, [], []]]]]]]]]]]]
>>> vine2tree(pseudo_node, 11)
>>> pseudo_node[2]
[4, [2, [1, [], []], [3, [], []]], [7, [6, [5, [], []], []], [8, [], [9, [], [10, [], []]]]]]
>>>

つまり無事に
　　4
　2　　7
1　3　6 　8
　　　5 　　9
　　　　　　　10

と言うバランスの二分木に変換されています(これが完全な平衡木かどうかは議論の余地があるだろうし、Wikipediaには後に改良版の論文が発表された、と注釈してるが、その疑似コードは残念ながら書かれてない)。

Wikipediaの疑似コードは結構分かりやすいんで、そのままプログラムしていけば一丁上がり、ですよ。
(Javaのリストは直接書き上げられないんで不便ですけどね。)

No.1 回答者： kmee 回答日時： 2021/07/22 11:46

追加の順番で実現するなら

中央値を追加
　上で追加した中央値より小さい値を、同じアルゴリズムで順番に追加
　上で追加した中央値より大きい値を、同じアルゴリズムで順番に追加

よく使われるのは、追加自体に工夫をするもの。
詳しくは「二分探索木 平衡化」で検索