바이너리 트리의 밸런스 여부를 확인하는 방법
그 학창 시절부터 꽤 오래됐다.병원에서 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) 왼쪽과 오른쪽 자녀의 키가 균형을 이루고 왼쪽 트리의 높이가 오른쪽 트리 높이의 1 이내인 경우 "높이 균형"이라고 합니다.
사양이 갖추어졌기 때문에, 코드는 간단하게 쓸 수 있습니다.사양에 따르기만 하면 됩니다.
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개의 깊은 노드처럼요이 알고리즘에 의해 스택이 파괴되는 시나리오가 있습니까?대규모 불균형 트리가 제공되어도 스택이 무너지지 않도록 구현을 수정할 수 있습니까?
업데이트: Donal Fellows는 답변에서 선택할 수 있는 '균형'의 정의는 다양하다고 지적합니다.예를 들어, "높이 균형"을 보다 엄격하게 정의하여 가장 가까운 빈 아이에 대한 경로 길이가 가장 먼 빈 아이에 대한 경로 중 하나 안에 있어야 할 수 있습니다.내 정의는 그것보다 덜 엄격해서 더 많은 나무를 수용할 수 있다.
또한 균형 트리는 각 분기의 빈 트리에 대한 최대 경로 길이가 2개 또는 3개 또는 기타 상수만큼 차이가 나지 않는 트리라고 할 수 있습니다.또는 최대 경로 길이가 최소 경로 길이의 일부(예: 1/2 또는 1/4)인 경우도 있습니다.
보통 때는 별로 중요하지 않아요.트리 밸런싱 알고리즘의 요점은 한쪽에는 100만 개의 노드가 있고 다른 한쪽에는 3개의 노드가 있는 상황이 발생하지 않도록 하는 것입니다.Donal의 정의는 이론적으로는 괜찮지만, 실제로는 그 정도의 엄격함을 만족시키는 트리 밸런싱 알고리즘을 고안하는 것은 골칫거리입니다.성능 절감은 일반적으로 구현 비용을 정당화하지 못합니다.실제로는 거의 차이가 없는 균형 수준을 얻기 위해 불필요한 트리 재배치를 하는 데 많은 시간을 할애합니다.이론적으로 완벽하게 균형 잡힌 나무에는 20개밖에 걸리지 않는데, 때때로 백만 개의 나무에서 가장 먼 잎사귀에 도달하는 데 40개의 가지가 필요할 때 누가 상관하겠는가?중요한 건 백만 달러도 안 든다는 거야최악의 경우 100만 명에서 최악의 경우 40명까지 줄이는 것이 보통 충분합니다. 최적의 경우까지 갈 필요는 없습니다.
균형은 정말 미묘한 특성이다. 당신은 그것이 무엇인지 안다고 생각하지만, 너무 쉽게 틀린다.특히 에릭 리퍼트의 답변조차 빗나갔다.그것은 키에 대한 개념이 충분하지 않기 때문이다.트리의 최소 높이 및 최대 높이 개념이 필요합니다(최소 높이는 루트부터 리프까지의 최소 단계 수, 최대값은...).자, 이제 아시겠죠?이 경우 균형은 다음과 같이 정의할 수 있습니다.
분기의 최대 높이가 분기의 최소 높이보다 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;
}
});
}
}
옵저버 패턴을 사용하지 않고도 할 수 있을 것 같은데, 이렇게 추론하는 게 더 쉬울 것 같아요.
[편집]: 왜 양쪽의 높이를 재지 못하는 거죠?다음 트리를 고려합니다.
/\
/ \
/ \
/ \_____
/\ / \_
/ \ / / \
/\ C /\ / \
/ \ / \ /\ /\
A B D E F G H J
잡혀 있습니다. 즉, ,, 지, 금, 조, 조, 조, ok, ok, ok, ok, ok이다.C2, 아깝다.A,B,D,E과 깊이 3입니다.F,G,H,J깊이 4입니다.왼쪽 가지 높이는 2(브랜치를 통과할수록 높이가 감소함)이고 오른쪽 가지 높이는 3입니다.그러나 전체 트리는 2의 높이 차이가 있기 때문에 균형이 맞지 않습니다.C ★★★★★★★★★★★★★★★★★」Fminimax 사양이 필요합니다(단, 2개의 높이만 허용되므로 실제 알고리즘은 덜 복잡할 수 있습니다).
이는 트리의 최상위 레벨이 균형을 이루고 있는지 여부만 결정합니다.즉, 왼쪽 끝과 오른쪽 끝에 두 개의 긴 가지가 있고, 중간에 아무것도 없는 나무가 있을 수 있습니다. 그러면 이것이 사실로 돌아갑니다. '를 확인해야 .root.left ★★★★★★★★★★★★★★★★★」root.right내적으로도 균형이 잡혀 있는지 확인하려고 합니다.
포스트오더 솔루션, 트리를 한 번만 통과합니다.시간의 복잡성은 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);
}
}
보너스 운동 응답.심플한 솔루션실제 구현에서는 사용자가 응답에 키를 포함시킬 필요가 없도록 이 또는 다른 것을 포장할 수 있습니다.
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
높이 균형 이진 트리의 정의는 다음과 같습니다.
각 노드의 2개의 서브트리의 높이가 1을 넘지 않는 바이너리 트리.
따라서 빈 이진 트리는 항상 높이 균형을 유지합니다.
비어 있지 않은 이진 트리는 다음과 같은 경우 높이 균형 조정됩니다.
- 왼쪽 서브트리는 높이 균형이 잡혀 있습니다.
- 오른쪽 서브트리는 높이 균형이 잡혀 있습니다.
- 왼쪽과 오른쪽 서브트리의 높이 차이는 1을 넘지 않습니다.
트리에 대해 생각해 봅시다.
A
\
B
/ \
C D
의 .A는 높이 균형(비어 있음)이 잡혀 있으며 오른쪽 서브트리도 마찬가지입니다.가 3이므로 되지 않기 높이 않습니다.0는 """입니다.2.
또한 다음 트리는 좌우 서브트리의 높이가 같아도 높이 균형이 맞지 않습니다.기존 코드가 true로 반환됩니다.
A
/ \
B C
/ \
D G
/ \
E H
그래서 방어에 있는 모든 단어는 매우 중요하다.
이 조작은 유효합니다.
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);
}
바이너리 트리가 균형 잡혀 있는지 여부를 레벨 순서 트래버설로 확인할 수 있는 경우:
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;
}
이것은 실제보다 훨씬 더 복잡하게 만들어지고 있다.
알고리즘은 다음과 같습니다.
- A = 최상위 노드의 깊이
B = 최하위 노드의 깊이
abs(A-B) < = 1이면 트리의 균형이 유지됩니다.
균형잡힌 의미는 눈앞의 구조에 따라 약간 다릅니다.예를 들어 A B-Tree에는 루트에서 특정 깊이 이상의 노드를 포함할 수 없습니다. 이 경우 모든 데이터는 루트에서 고정된 깊이에서 유지되지만 Leave-But-One 노드로의 분포가 고르지 않으면 균형을 잃을 수 있습니다.스킵 리스트는 전혀 균형 잡힌 개념이 없으며, 대신 적절한 성과를 달성할 확률에 의존합니다.Fibonacci 트리는 의도적으로 균형을 잃고 때때로 더 긴 업데이트를 대가로 뛰어난 점근 성능을 달성하기 위해 재조정을 지연시킵니다.AVL 및 Red-Black 트리는 깊이 밸런스의 불변성을 얻기 위해 메타데이터를 각 노드에 부가합니다.
이러한 모든 구조 및 그 이상은 가장 일반적인 프로그래밍 시스템의 표준 라이브러리에 있습니다(python, RAGE! 제외).1개 또는 2개를 실장하는 것은 좋은 프로그래밍 방법이지만, 시판되는 컬렉션에서 해결할 수 없는 특수한 퍼포먼스를 가지고 있지 않는 한, 실전 가동에 시간을 낭비하는 것은 좋지 않을 것입니다.
주 1: 서브트리의 높이는 한 번만 계산됩니다.
주 2: 왼쪽 서브트리가 언밸런스일 경우 수백만 개의 요소를 포함할 가능성이 있는 오른쪽 서브트리의 계산은 건너뜁니다.
// 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/Red-Black).사실 자바 트리는 균형이 잡혀 있습니다.
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));
}
다음은 C#의 테스트 완료 솔루션(Java dev가 아닙니다)입니다(콘솔 앱에 복사 붙여넣기만 하면 됩니다).균형에 대한 정의는 모든 사람이 만족하는 것은 아니지만, 재귀적인 루프에서 깊이/높이를 체크하고 각 노드의 높이/레벨/깊이를 저장하지 않고 첫 번째 불일치로 종료하는 약간 다른 접근방식을 살펴보세요(함수 호출에서만 유지).
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);
}
}
}
}
만약 이것이 당신의 일이라면, 저는 다음을 제안합니다.
- 수레바퀴를 재창조하지 않고
- 비트를 만지작거리지 않고 COTS를 사용/구매합니다.
- 비즈니스 문제 해결에 필요한 시간과 에너지를 절약할 수 있습니다.
#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;
}
RE: BFS를 사용하여 레벨 오더 트래버설을 실행하는 @lucky의 솔루션.
트리를 이동하고 노드가 리프인 최소 수준을 설명하는 변수 최소/최대 수준에 대한 참조를 유지합니다.
@lucky 솔루션은 수정이 필요하다고 생각합니다.@codaddict에서 제시된 바와 같이 노드가 리프인지 아닌지를 확인하는 것이 아니라 왼쪽 또는 오른쪽 중 하나의 자녀(둘 다 아님)가 늘인지 확인해야 합니다.그렇지 않으면 알고리즘은 이 트리를 유효한 균형 트리로 간주합니다.
1
/ \
2 4
\ \
3 1
Python의 경우:
def is_bal(root):
if root is None:
return True
import queue
Q = queue.Queue()
Q.put(root)
level = 0
min_level, max_level = sys.maxsize, sys.minsize
while not Q.empty():
level_size = Q.qsize()
for i in range(level_size):
node = Q.get()
if not node.left or node.right:
min_level, max_level = min(min_level, level), max(max_level, level)
if node.left:
Q.put(node.left)
if node.right:
Q.put(node.right)
level += 1
if abs(max_level - min_level) > 1:
return False
return True
이 솔루션은 O(n) 시간 및 O(n) 공간에서 작동하며 첫 번째 질문에 제시된 모든 요구사항을 충족해야 합니다.메모리 오버플로는 재귀 콜스택을 블로우하지 않고 힙으로 전송됩니다.
또는 처음에 트리를 이동하여 각 루트 서브트리에 대해 + 캐시 최대 높이를 반복적으로 계산할 수도 있습니다.그런 다음 다른 반복 실행에서 각 루트의 왼쪽 및 오른쪽 하위 트리의 캐시 높이가 두 개 이상 차이가 나지 않는지 확인합니다.이것은 O(n) 시간 및 O(n) 공간에서도 실행되지만 스택 오버플로를 일으키지 않도록 반복됩니다.
음, 좌우의 높이와 좌우의 균형이 잡혀 있는지 확인할 수 있는 방법이 필요합니다.
난 그냥 ★★★★★★★★★★★★★★★★★★★★★★★★★★★」return height(node->left) == height(node->right);
의 height함수, 읽기:재귀에 대해서
어떤 종류의 나무를 말씀하시는 겁니까?저 밖에는 스스로 균형을 잡는 나무들이 있다.균형을 유지하기 위해 트리의 순서를 변경할 필요가 있는지 여부를 결정하는 알고리즘을 확인합니다.
다음은 일반적인 깊이 우선 트래버설에 기반한 버전입니다.다른 정답보다 빠르고 언급된 모든 "과제"를 처리해야 합니다.스타일은 죄송합니다.저는 자바어를 잘 모릅니다.
max와 min이 모두 설정되어 있고 차이가 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 );
}
class Node {
int data;
Node left;
Node right;
// assign variable with constructor
public Node(int data) {
this.data = data;
}
}
public class BinaryTree {
Node root;
// get max depth
public static int maxDepth(Node node) {
if (node == null)
return 0;
return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}
// get min depth
public static int minDepth(Node node) {
if (node == null)
return 0;
return 1 + Math.min(minDepth(node.left), minDepth(node.right));
}
// return max-min<=1 to check if tree balanced
public boolean isBalanced(Node node) {
if (Math.abs(maxDepth(node) - minDepth(node)) <= 1)
return true;
return false;
}
public static void main(String... strings) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
if (tree.isBalanced(tree.root))
System.out.println("Tree is balanced");
else
System.out.println("Tree is 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
}
public int height(Node node){
if(node==null)return 0;
else{
int l=height(node.leftChild);
int r=height(node.rightChild);
return(l>r?l+1:r+1);
}}
public boolean balanced(Node n){
int l= height(n.leftChild);
int r= height(n.rightChild);
System.out.println(l + " " +r);
if(Math.abs(l-r)>1)
return false;
else
return true;
}
빈 트리는 높이 균형을 잡습니다.비어 있지 않은 이진 트리 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)
특히 큰 트리에서 성능을 향상시키려면 각 노드의 높이를 저장하여 공간 균형을 맞출 수 있습니다.
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;
}
각 서브트리의 밸런스 여부를 재귀적으로 확인합니다.재귀란 서브트리에 무언가를 요청하면 서브트리가 응답을 반환하는 것을 의미합니다.베이스 케이스를 칠 때까지 계속 물어보는군요.트리 질문의 기본 케이스는 리프 노드를 누를 때입니다.
이 경우 서브트리에 다음 2가지 질문을 합니다.
1-균형이 잡혀있습니까?
2-키가 어떻게 되세요?
따라서 재귀 함수는 2개의 답을 반환하고 저는 그 답을 배열에 저장합니다.
다음은 python 코드입니다.
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def dfs(root):
# leaf node is balanced
if not root:
# we carry the height of each subtree
return [True,0]
# with recursion, we start from bottom, so we do not have repetitive work
left,right=dfs(root.left),dfs(root.right)
# if any of the subtree return false, then we know entire tree is not balanced
balanced=left[0] and right[0] and abs(left[1]-right[1])<=1
# 1+max(left[1],right[1]) is the height of the each subtree. 1 is the root of the subtree
return [balanced,1+max(left[1],right[1])]
return dfs(root)[0]
javascript 코드입니다.
var isBalanced = function(root) {
function dfs(root){
if(!root){
return [true,0]
}
const left=dfs(root.left)
const right=dfs(root.right)
const balanced=left[0] && right[0] && Math.abs(left[1]-right[1])<=1
return [balanced,1+Math.max(left[1],right[1])]
}
return dfs(root)[0]
};
높이 균형 이진 트리는 각 노드의 두 하위 트리의 깊이가 하나 이상 다르지 않은 이진 트리이다.
여기 트리 노드가 있습니다.
public class TreeNode
{
public int Value;
public TreeNode Left;
public TreeNode Right;
public TreeNode(int value)
{
Value = value;
}
}
public bool IsBalanced(TreeNode root)
{
if(root == null)
{
return true;
}
var left = Depth(root.Left);
var right = Depth(root.Right);
if(Math.Abs(left - right) > 1)
{
return false;
}
return IsBalanced(root.Left) && IsBalanced(root.Right);
}
private int Depth(TreeNode node)
{
if(node == null)
{
return 0;
}
return Math.Max(Depth(node.Left), Depth(node.Right)) + 1;
}
여기서 연습해 보세요
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 );
균형이 맞지 않는 트리는 항상 실패합니다.
언급URL : https://stackoverflow.com/questions/742844/how-to-determine-if-binary-tree-is-balanced
'source' 카테고리의 다른 글
| groupBy에서 발생한 횟수를 어떻게 셀 수 있습니까? (0) | 2022.10.27 |
|---|---|
| Java에 파일이 있는지 확인하려면 어떻게 해야 하나요? (0) | 2022.10.27 |
| mysql의 SERIAL과 AUTO_INCREMENT의 차이점은 무엇입니까? (0) | 2022.10.27 |
| MySQL: 가져올 때 오류 무시? (0) | 2022.10.27 |
| Linux용 무료 경량 MySQL GUI를 추천해 주시겠습니까? (0) | 2022.10.27 |