Trädegenskaper: djup, höjd och storlek

Ett träds form påverkar ofta algoritmens kostnad. I ett kort, balanserat träd går det att ta sig ned på få nivåer. Ett avlångt kedjeformat träd kan kräva sökning bland nästan alla noder.

Definitioner

Om roten har djup 0 har varje barn djupet ett mer än sin förälder. Trädets höjd är det största djupet bland löven, mätt i kanter. Ett träd med en nod har då höjd 0. För tomma träd används ibland höjd -1, men definitionen måste vara tydlig.

Storlek är antalet noder. Ett ändligt rotat träd med minst en nod har storlek - 1 kanter. Det räcker dock inte ensamt för att avgöra om en graf är ett träd: den måste också vara sammanhängande och utan cykler.

Räkneexempel

Anta att R har barnen A och B, A har C och C har D. Djupen blir R=0, A=1, B=1, C=2 och D=3. Trädets höjd är 3, storleken är 5 och antalet kanter är 4. Trädet är inte balanserat runt R eftersom vänster del går betydligt djupare.

Beräkna höjden

En rekursiv funktion beräknar barnens höjd. Ett löv ger höjd noll kanter, medan en inre nod ger ett plus största barnhöjden. Exemplet med binära träd mäter höjden i kanter och använder -1 för ett tomt delträd.

C#

C# | Height.cs

using System.Collections.Generic;

public sealed class Node
{
    public int Value { get; }
    public Node? Left { get; set; }
    public Node? Right { get; set; }
    public Node(int value) => Value = value;
}

static int Height(Node? node) => node is null ? -1 :
    1 + Math.Max(Height(node.Left), Height(node.Right));

C++

C++ | Height.cpp

#include <memory>
#include <vector>

struct Node {
    int value;
    std::unique_ptr<Node> left, right;
    explicit Node(int value) : value(value) {}
};

#include <algorithm>
int height(const Node* node) {
    if (!node) return -1;
    return 1 + std::max(height(node->left.get()), height(node->right.get()));
}

Alla noder besöks en gång, alltså O(n) tid. Rekursionsstacken använder O(h) extra minne för höjd h, där skillnaden mellan höjd i noder och kanter bara är en konstant. Ett kedjeformat träd kan använda O(n) stackutrymme. Trädets ursprungliga lagring räknas inte som extraminne.

Vanliga förväxlingar

En nods djup och höjd är olika begrepp. Ett välbalanserat binärt träd har höjd O(log n), men ett godtyckligt binärt träd behöver inte vara balanserat. Ordet binärt garanterar inte logaritmisk prestanda.

Läs vidare om binära trädtyper och traversering.