あの学年から久しぶりです。病院でITスペシャリストとして就職。今、実際のプログラミングを行うために移動しようとしています。私は現在二分木に取り組んでおり、木が高さのバランスが取れているかどうかを判断するための最良の方法は何でしょうか。
私はこれに沿って何かを考えていました：
public boolean isBalanced(Node root){
if(root==null){
return true; //tree is empty
}
else{
int lh = root.left.height();
int rh = root.right.height();
if(lh - rh > 1 || rh - lh > 1){
return false;
}
}
return true;
}
これは良い実装ですか？または私は何かが欠けていますか？
何か他のものを探しているときに、この古い質問に出くわしました。完全な答えが得られなかったことに気付きました。
この問題を解決する方法は、作成しようとしている関数の仕様を作成することから始めることです。
仕様: 整形式のバイナリ ツリーは、(1) 空である、または (2) 左右の子の高さがバランスが取れており、左側のツリーの高さが右の木の高さ。
仕様ができたので、コードを書くのは簡単です。仕様に従ってください：
IsHeightBalanced(tree)
return (tree is empty) or
(IsHeightBalanced(tree.left) and
IsHeightBalanced(tree.right) and
abs(Height(tree.left) - Height(tree.right)) <= 1)
それを選択したプログラミング言語に翻訳するのは簡単です。
ボーナス演習: この素朴なコード スケッチは、高さを計算するときにツリーを何度もトラバースします。より効率的にすることはできますか？
スーパー ボーナス エクササイズ: 木が非常にバランスが悪いとします。同様に、片側に 100 万ノードの深さ、反対側に 3 つの深さがあります。このアルゴリズムがスタックを吹き飛ばすシナリオはありますか? 非常に不均衡なツリーが与えられた場合でも、スタックを爆破しないように実装を修正できますか?
UPDATE : Donal Fellows は、彼の回答の中で、選択できる「バランスのとれた」にはさまざまな定義があると指摘しています。たとえば、「高さのバランス」をより厳密に定義し、最も近い空の子へのパスの長さが、最も遠い空の子へのパスの 1 つ以内であることを要求できます。私の定義はそれよりも厳密ではないため、より多くのツリーを許可します。
私の定義よりも厳密ではない場合もあります。バランスの取れたツリーとは、各ブランチの空のツリーへの最大パス長の差が 2、3、またはその他の定数を超えないツリーであると言えます。または、最大パス長が最小パス長の半分または 4 分の 1 などの分数であること。
普段は全く関係ありません。ツリー バランシング アルゴリズムのポイントは、片側に 100 万個のノードがあり、反対側に 3 つのノードがあるという状況にならないようにすることです。Donal の定義は理論上は問題ありませんが、実際には、そのレベルの厳密さを満たすツリー バランシング アルゴリズムを考え出すのは困難です。パフォーマンスの節約は、通常、実装コストを正当化するものではありません。実際にはほとんど違いがないレベルのバランスを達成するために、不必要なツリーの再配置に多くの時間を費やします。理論的には、完全にバランスの取れたツリーでは 20 個しか必要ないのに、100 万ノードの不完全にバランスの取れたツリーで最も遠い葉に到達するのに 40 個のブランチが必要になる場合があることを誰が気にしますか? ポイントは、100万もかからないということです。通常は、最悪の場合の 100 万から 40 の最悪の場合で十分です。最適なケースまで行く必要はありません。
バランスは本当に微妙な特性です。あなたはそれが何であるかを知っていると思っていますが、間違っているのはとても簡単です. 特に、Eric Lippert の (良い) 回答でさえオフです。それは、高さの概念が十分でないためです。木の高さの最小値と最大値の概念が必要です (最小の高さは、根から葉までの最小のステップ数であり、最大の高さは... わかります)。それを考えると、バランスを次のように定義できます。
枝の最大の高さが、枝の最小の高さの1 つを超えない木。
(これは実際には、ブランチ自体がバランスが取れていることを意味します。最大と最小の両方で同じブランチを選択できます。)
このプロパティを確認するために必要なのは、現在の深さを追跡する単純なツリー トラバーサルだけです。最初にバックトラックすると、ベースラインの深さが得られます。その後バックトラックするたびに、新しい深さをベースラインと比較します
コード内:
class Tree {
Tree left, right;
static interface Observer {
public void before();
public void after();
public boolean end();
}
static boolean traverse(Tree t, Observer o) {
if (t == null) {
return o.end();
} else {
o.before();
try {
if (traverse(left, o))
return traverse(right, o);
return false;
} finally {
o.after();
}
}
}
boolean balanced() {
final Integer[] heights = new Integer[2];
return traverse(this, new Observer() {
int h;
public void before() { h++; }
public void after() { h--; }
public boolean end() {
if (heights[0] == null) {
heights[0] = h;
} else if (Math.abs(heights[0] - h) > 1) {
return false;
} else if (heights[0] != h) {
if (heights[1] == null) {
heights[1] = h;
} else if (heights[1] != h) {
return false;
}
}
return true;
}
});
}
}
Observer パターンを使用せずにこれを行うこともできると思いますが、この方法で推論する方が簡単だと思います。
[編集]: なぜ各辺の高さを測れないのですか? このツリーを考えてみましょう:
/\
/ \
/ \
/ \_____
/\ / \_
/ \ / / \
/\ C /\ / \
/ \ / \ /\ /\
A B D E F G H J
OK、少し乱雑ですが、根の各辺はバランスが取れています:Cは深さ 2、A、B、は深さ 3、、、Dは深さ 4 です。枝)、右の枝の高さは 3ですが、 と の高さの差が 2 あり、ツリー全体のバランスが取れていません。ミニマックス仕様が必要です (ただし、許可される高さは 2 つだけであるため、実際のアルゴリズムはそれほど複雑ではありません)。EFGHJCF
これは、ツリーのトップレベルのバランスが取れているかどうかを判断するだけです。つまり、左端と右端に2つの長い枝があり、中央に何もないツリーを作成できます。これにより、trueが返されます。trueを返す前に、を再帰的にチェックし、root.leftそれらが内部的にバランスが取れているかどうかを確認する必要があります。root.right
ボーナス行使応答。簡単な解決策。明らかに、実際の実装では、これまたは何かをラップして、ユーザーが応答に高さを含める必要がないようにすることができます。
IsHeightBalanced(tree, out height)
if (tree is empty)
height = 0
return true
balance = IsHeightBalanced(tree.left, out heightleft) and IsHeightBalanced(tree.right, out heightright)
height = max(heightleft, heightright)+1
return balance and abs(heightleft - heightright) <= 1
ポスト オーダー ソリューション、ツリーを 1 回だけトラバースします。時間の複雑さは O(n)、空間は O(1)、トップダウン ソリューションよりも優れています。Javaバージョンの実装を提供します。
public static <T> boolean isBalanced(TreeNode<T> root){
return checkBalance(root) != -1;
}
private static <T> int checkBalance(TreeNode<T> node){
if(node == null) return 0;
int left = checkBalance(node.getLeft());
if(left == -1) return -1;
int right = checkBalance(node.getRight());
if(right == -1) return -1;
if(Math.abs(left - right) > 1){
return -1;
}else{
return 1 + Math.max(left, right);
}
}
高さのバランスが取れた二分木の定義は次のとおりです。
すべてのノードの 2 つのサブツリーの高さが1 を超えないバイナリ ツリー。
したがって、空の二分木は常に高さのバランスが取れています。
次の場合、空でない二分木は高さのバランスがとれています。
ツリーを考えてみましょう:
A
\
B
/ \
C D
ご覧のとおり、 の左側のサブツリーはA(空であるため) 高さのバランスが取れており、右側のサブツリーも高さのバランスが取れています。0ただし、左サブツリーの高さが であり、右サブツリーの高さが であるため、条件 3 が満たされないため、ツリーの高さのバランスは取れていません2。
また、次のツリーは、左右のサブツリーの高さが等しいにもかかわらず、高さのバランスが取れていません。既存のコードは true を返します。
A
/ \
B C
/ \
D G
/ \
E H
したがって、def のeveryという言葉は非常に重要です。
これはうまくいきます：
int height(treeNodePtr root) {
return (!root) ? 0: 1 + MAX(height(root->left),height(root->right));
}
bool isHeightBalanced(treeNodePtr root) {
return (root == NULL) ||
(isHeightBalanced(root->left) &&
isHeightBalanced(root->right) &&
abs(height(root->left) - height(root->right)) <=1);
}
二分木がバランスが取れているかどうかは、Level order traversal で確認できます。
private boolean isLeaf(TreeNode root) {
if (root.left == null && root.right == null)
return true;
return false;
}
private boolean isBalanced(TreeNode root) {
if (root == null)
return true;
Vector<TreeNode> queue = new Vector<TreeNode>();
int level = 1, minLevel = Integer.MAX_VALUE, maxLevel = Integer.MIN_VALUE;
queue.add(root);
while (!queue.isEmpty()) {
int elementCount = queue.size();
while (elementCount > 0) {
TreeNode node = queue.remove(0);
if (isLeaf(node)) {
if (minLevel > level)
minLevel = level;
if (maxLevel < level)
maxLevel = level;
} else {
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
elementCount--;
}
if (abs(maxLevel - minLevel) > 1) {
return false;
}
level++;
}
return true;
}
これは、実際よりもはるかに複雑になっています。
アルゴリズムは次のとおりです。
B = 最下位ノードの深さ
abs(AB) <= 1 の場合、ツリーはバランスが取れています
バランスのとれた意味は、手元の構造によって少し異なります。たとえば、B ツリーは、ルートから特定の深さを超えるノードを持つことはできません。さらに言えば、すべてのデータはルートから固定された深さに存在しますが、葉から葉への分布が異なる場合、バランスが崩れる可能性があります。 -but-1 つのノードが不均一です。スキップリスト バランスの概念がまったくなく、代わりに確率に頼って適切なパフォーマンスを達成します。フィボナッチ ツリーは意図的にバランスを崩し、リバランスを延期して、より長い更新と引き換えに優れた漸近的なパフォーマンスを実現します。AVL および Red-Black ツリーは、各ノードにメタデータを添付して、深度バランスの不変条件を実現します。
これらすべての構造体とそれ以上のものは、ほとんどの一般的なプログラミング システム (python、RAGE を除く) の標準ライブラリに存在します。1 つまたは 2 つを実装することは良いプログラミング手法ですが、既成のコレクションで満足する必要のない独特のパフォーマンスが問題にある場合を除き、本番用に独自のものを作成するのはおそらく時間の無駄です。
注 1: サブツリーの高さは 1 回だけ計算されます。
注 2: 左側のサブツリーが不均衡である場合、100 万個の要素を含む可能性がある右側のサブツリーの計算はスキップされます。
// return height of tree rooted at "tn" if, and only if, it is a balanced subtree
// else return -1
int maxHeight( TreeNode const * tn ) {
if( tn ) {
int const lh = maxHeight( tn->left );
if( lh == -1 ) return -1;
int const rh = maxHeight( tn->right );
if( rh == -1 ) return -1;
if( abs( lh - rh ) > 1 ) return -1;
return 1 + max( lh, rh );
}
return 0;
}
bool isBalanced( TreeNode const * root ) {
// Unless the maxHeight is -1, the subtree under "root" is balanced
return maxHeight( root ) != -1;
}
バランスは通常、各方向の最長パスの長さに依存します。上記のアルゴリズムはあなたのためにそれをするつもりはありません。
何を実装しようとしていますか？周りには平衡二分木があります（AVL /赤黒）。実際、Javaツリーはバランスが取れています。
これは、C＃で完全にテストされたソリューションです（申し訳ありませんが、Java開発者ではありません）（コンソールアプリにコピーして貼り付けるだけです）。バランスの取れた定義はさまざまであるため、誰もが私のテスト結果を気に入るとは限りませんが、再帰ループで深さ/高さをチェックし、各ノードのノードの高さ/レベル/深さを保存せずに最初の不一致で終了するという、わずかに異なるアプローチを見てください。 （関数呼び出しでのみ維持します）。
using System;
using System.Linq;
using System.Text;
namespace BalancedTree
{
class Program
{
public static void Main()
{
//Value Gathering
Console.WriteLine(RunTreeTests(new[] { 0 }));
Console.WriteLine(RunTreeTests(new int[] { }));
Console.WriteLine(RunTreeTests(new[] { 0, 1, 2, 3, 4, -1, -4, -3, -2 }));
Console.WriteLine(RunTreeTests(null));
Console.WriteLine(RunTreeTests(new[] { 10, 8, 12, 8, 4, 14, 8, 10 }));
Console.WriteLine(RunTreeTests(new int[] { 20, 10, 30, 5, 15, 25, 35, 3, 8, 12, 17, 22, 27, 32, 37 }));
Console.ReadKey();
}
static string RunTreeTests(int[] scores)
{
if (scores == null || scores.Count() == 0)
{
return null;
}
var tree = new BinarySearchTree();
foreach (var score in scores)
{
tree.InsertScore(score);
}
Console.WriteLine(tree.IsBalanced());
var sb = tree.GetBreadthWardsTraversedNodes();
return sb.ToString(0, sb.Length - 1);
}
}
public class Node
{
public int Value { get; set; }
public int Count { get; set; }
public Node RightChild { get; set; }
public Node LeftChild { get; set; }
public Node(int value)
{
Value = value;
Count = 1;
}
public override string ToString()
{
return Value + ":" + Count;
}
public bool IsLeafNode()
{
return LeftChild == null && RightChild == null;
}
public void AddValue(int value)
{
if (value == Value)
{
Count++;
}
else
{
if (value > Value)
{
if (RightChild == null)
{
RightChild = new Node(value);
}
else
{
RightChild.AddValue(value);
}
}
else
{
if (LeftChild == null)
{
LeftChild = new Node(value);
}
else
{
LeftChild.AddValue(value);
}
}
}
}
}
public class BinarySearchTree
{
public Node Root { get; set; }
public void InsertScore(int score)
{
if (Root == null)
{
Root = new Node(score);
}
else
{
Root.AddValue(score);
}
}
private static int _heightCheck;
public bool IsBalanced()
{
_heightCheck = 0;
var height = 0;
if (Root == null) return true;
var result = CheckHeight(Root, ref height);
height--;
return (result && height == 0);
}
private static bool CheckHeight(Node node, ref int height)
{
height++;
if (node.LeftChild == null)
{
if (node.RightChild != null) return false;
if (_heightCheck != 0) return _heightCheck == height;
_heightCheck = height;
return true;
}
if (node.RightChild == null)
{
return false;
}
var leftCheck = CheckHeight(node.LeftChild, ref height);
if (!leftCheck) return false;
height--;
var rightCheck = CheckHeight(node.RightChild, ref height);
if (!rightCheck) return false;
height--;
return true;
}
public StringBuilder GetBreadthWardsTraversedNodes()
{
if (Root == null) return null;
var traversQueue = new StringBuilder();
traversQueue.Append(Root + ",");
if (Root.IsLeafNode()) return traversQueue;
TraversBreadthWards(traversQueue, Root);
return traversQueue;
}
private static void TraversBreadthWards(StringBuilder sb, Node node)
{
if (node == null) return;
sb.Append(node.LeftChild + ",");
sb.Append(node.RightChild + ",");
if (node.LeftChild != null && !node.LeftChild.IsLeafNode())
{
TraversBreadthWards(sb, node.LeftChild);
}
if (node.RightChild != null && !node.RightChild.IsLeafNode())
{
TraversBreadthWards(sb, node.RightChild);
}
}
}
}
public boolean isBalanced(TreeNode root)
{
return (maxDepth(root) - minDepth(root) <= 1);
}
public int maxDepth(TreeNode root)
{
if (root == null) return 0;
return 1 + max(maxDepth(root.left), maxDepth(root.right));
}
public int minDepth (TreeNode root)
{
if (root == null) return 0;
return 1 + min(minDepth(root.left), minDepth(root.right));
}
これがあなたの仕事のためなら、私はお勧めします：
#include <iostream>
#include <deque>
#include <queue>
struct node
{
int data;
node *left;
node *right;
};
bool isBalanced(node *root)
{
if ( !root)
{
return true;
}
std::queue<node *> q1;
std::queue<int> q2;
int level = 0, last_level = -1, node_count = 0;
q1.push(root);
q2.push(level);
while ( !q1.empty() )
{
node *current = q1.front();
level = q2.front();
q1.pop();
q2.pop();
if ( level )
{
++node_count;
}
if ( current->left )
{
q1.push(current->left);
q2.push(level + 1);
}
if ( current->right )
{
q1.push(current->right);
q2.push(level + 1);
}
if ( level != last_level )
{
std::cout << "Check: " << (node_count ? node_count - 1 : 1) << ", Level: " << level << ", Old level: " << last_level << std::endl;
if ( level && (node_count - 1) != (1 << (level-1)) )
{
return false;
}
last_level = q2.front();
if ( level ) node_count = 1;
}
}
return true;
}
int main()
{
node tree[15];
tree[0].left = &tree[1];
tree[0].right = &tree[2];
tree[1].left = &tree[3];
tree[1].right = &tree[4];
tree[2].left = &tree[5];
tree[2].right = &tree[6];
tree[3].left = &tree[7];
tree[3].right = &tree[8];
tree[4].left = &tree[9]; // NULL;
tree[4].right = &tree[10]; // NULL;
tree[5].left = &tree[11]; // NULL;
tree[5].right = &tree[12]; // NULL;
tree[6].left = &tree[13];
tree[6].right = &tree[14];
tree[7].left = &tree[11];
tree[7].right = &tree[12];
tree[8].left = NULL;
tree[8].right = &tree[10];
tree[9].left = NULL;
tree[9].right = &tree[10];
tree[10].left = NULL;
tree[10].right= NULL;
tree[11].left = NULL;
tree[11].right= NULL;
tree[12].left = NULL;
tree[12].right= NULL;
tree[13].left = NULL;
tree[13].right= NULL;
tree[14].left = NULL;
tree[14].right= NULL;
std::cout << "Result: " << isBalanced(tree) << std::endl;
return 0;
}
さて、あなたは左右の高さを決定する方法が必要です、そして左右がバランスが取れているかどうか。
そして、私はただreturn height(node->left) == height(node->right);
height関数の
記述については、 「再帰を理解する」を参照してください。
どんな木を話しているの？そこには平衡二分木があります。バランスを維持するためにツリーを並べ替える必要があるかどうかを判断するアルゴリズムを確認してください。
これは、一般的な深さ優先トラバーサルに基づくバージョンです。他の正解よりも速く、言及されたすべての「課題」を処理する必要があります。スタイルについては申し訳ありませんが、私は Java をよく知りません。
最大値と最小値の両方が設定されていて、差が 1 より大きい場合は、早期に戻ることでさらに高速化できます。
public boolean isBalanced( Node root ) {
int curDepth = 0, maxLeaf = 0, minLeaf = INT_MAX;
if ( root == null ) return true;
while ( root != null ) {
if ( root.left == null || root.right == null ) {
maxLeaf = max( maxLeaf, curDepth );
minLeaf = min( minLeaf, curDepth );
}
if ( root.left != null ) {
curDepth += 1;
root = root.left;
} else {
Node last = root;
while ( root != null
&& ( root.right == null || root.right == last ) ) {
curDepth -= 1;
last = root;
root = root.parent;
}
if ( root != null ) {
curDepth += 1;
root = root.right;
}
}
}
return ( maxLeaf - minLeaf <= 1 );
}
Here's what i have tried for Eric's bonus exercise. I try to unwind of my recursive loops and return as soon as I find a subtree to be not balanced.
int heightBalanced(node *root){
int i = 1;
heightBalancedRecursive(root, &i);
return i;
}
int heightBalancedRecursive(node *root, int *i){
int lb = 0, rb = 0;
if(!root || ! *i) // if node is null or a subtree is not height balanced
return 0;
lb = heightBalancedRecursive(root -> left,i);
if (!*i) // subtree is not balanced. Skip traversing the tree anymore
return 0;
rb = heightBalancedRecursive(root -> right,i)
if (abs(lb - rb) > 1) // not balanced. Make i zero.
*i = 0;
return ( lb > rb ? lb +1 : rb + 1); // return the current height of the subtree
}
特に巨大なツリーでパフォーマンスを向上させるには、各ノードの高さを保存できるため、スペースとパフォーマンスのトレードオフになります。
class Node {
Node left;
Node right;
int value;
int height;
}
追加・削除の実装例
void addNode(Node root,int v)
{ int height =0;
while(root != null)
{
// Since we are adding new node so the height
// will increase by one in each node we will pass by
root.height += 1;
height++;
else if(v > root.value){
root = root.left();
}
else{
root = root.right();
}
}
height++;
Node n = new Node(v , height);
root = n;
}
int treeMaxHeight(Node root)
{
return Math.Max(root.left.height,root.right.height);
}
int treeMinHeight(Node root)
{
return Math.Min(root.left.height,root.right.height);
}
Boolean isNodeBlanced(Node root)
{
if (treeMaxHeight(root) - treeMinHeight(root) > 2)
return false;
return true;
}
Boolean isTreeBlanced (Node root)
{
if(root == null || isTreeBalanced(root.left) && isTreeBalanced(root.right) && isNodeBlanced(root))
return true;
return false;
}
空のツリーは高さのバランスが取れています。空でない二分木 T は、次の場合にバランスが取れています。
1) T の左部分木はバランスがとれている
2) T の右側の部分木はバランスがとれている
3) 左部分木と右部分木の高さの差が 1 以下。
/* program to check if a tree is height-balanced or not */
#include<stdio.h>
#include<stdlib.h>
#define bool int
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* The function returns true if root is balanced else false
The second parameter is to store the height of tree.
Initially, we need to pass a pointer to a location with value
as 0. We can also write a wrapper over this function */
bool isBalanced(struct node *root, int* height)
{
/* lh --> Height of left subtree
rh --> Height of right subtree */
int lh = 0, rh = 0;
/* l will be true if left subtree is balanced
and r will be true if right subtree is balanced */
int l = 0, r = 0;
if(root == NULL)
{
*height = 0;
return 1;
}
/* Get the heights of left and right subtrees in lh and rh
And store the returned values in l and r */
l = isBalanced(root->left, &lh);
r = isBalanced(root->right,&rh);
/* Height of current node is max of heights of left and
right subtrees plus 1*/
*height = (lh > rh? lh: rh) + 1;
/* If difference between heights of left and right
subtrees is more than 2 then this node is not balanced
so return 0 */
if((lh - rh >= 2) || (rh - lh >= 2))
return 0;
/* If this node is balanced and left and right subtrees
are balanced then return true */
else return l&&r;
}
/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main()
{
int height = 0;
/* Constructed binary tree is
1
/ \
2 3
/ \ /
4 5 6
/
7
*/
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->left->left->left = newNode(7);
if(isBalanced(root, &height))
printf("Tree is balanced");
else
printf("Tree is not balanced");
getchar();
return 0;
}
時間の複雑さ: O(n)
static boolean isBalanced(Node root) {
//check in the depth of left and right subtree
int diff = depth(root.getLeft()) - depth(root.getRight());
if (diff < 0) {
diff = diff * -1;
}
if (diff > 1) {
return false;
}
//go to child nodes
else {
if (root.getLeft() == null && root.getRight() == null) {
return true;
} else if (root.getLeft() == null) {
if (depth(root.getRight()) > 1) {
return false;
} else {
return true;
}
} else if (root.getRight() == null) {
if (depth(root.getLeft()) > 1) {
return false;
} else {
return true;
}
} else if (root.getLeft() != null && root.getRight() != null && isBalanced(root.getLeft()) && isBalanced(root.getRight())) {
return true;
} else {
return false;
}
}
}
これはうまくいきませんか？
return ( ( Math.abs( size( root.left ) - size( root.right ) ) < 2 );
アンバランスなツリーは常にこれに失敗します。