---
tags: Assignments
---
# Blatt 04

| Kurs | Semester | Team |
| ------------------------------- | -------- | -------------------------- |
| Algorithmen und Datenstrukturen | SS 2020 | Carlo Mohl & Noah Nuebling |

---

[TOC]

---

## Aufgabe 1

### a)

#### 1.

Die Eigenschaft eines binären Suchbaumes dass die Elemente in eine Richtung sortiert sind ist unvereinbar mit der Eigenschaft eines Heaps dass Wurzelelemente größer sind als ihre Kinder.
Das rechte Kind muss zugleich grösser sein (Suchbaum) und kleiner (Heap) sein.

        4
        
    3!!        6
    
1     4!!    5     

#### 2.

Selbe Begründung wie Teilaufgabe 1.

        3
        
    2        6
    
1         5.5    x

#### 3.

Wegen der AVL Eigenschaft müssen die Elemente in einem "Dreieck" angeordnet sein und daher gilt die selbe Begründung wie in Teilaufgabe 1.

    3
        
2       6

### b)

Das Sortieren von n Elementen ist in $\Omega(n \log n)$, egal welche Methode man benutzt. (Wurde in der Vorlesung bewiesen)
Ein Suchbaum ist sortiert, daher muss die Konstruktion eines Suchbaums aus einer unsortierten Menge auch in $\Omega(n \log n)$ sein.

## Aufgabe 2

### a)
Es funktioniert in allen Fällen ausser im 3.
Das Element 684 kommt im linken Kind von 679 vor, daher ist die Suchbaumeigenschaft nicht erfüllt.

### b)

def search_tree_path_is_valid(path):

    min = -math.inf
    max = math.inf

    for i in range(0, len(path) - 1):
        this = path[i]
        next = path[i+1]

        if this <= min or max <= this:
            return False

        if this < next:
            min = this
        elif this > next:
            max = this
        else:
            return "Invalid input"

	return True

## Aufgabe 3

### a)

__Beschreibung__
Wenn x ein rechtes Kind hat, geben wir das kleinste Element des rechten Teilbaums zurück.
Wenn x kein rechtes Kind hat, traversieren wir so lange die Elternknoten von x, bis wir einen Knoten finden, der größer ist, als der den wir uns zuvor angeschaut haben. Diesen geben wir dann zurück.
Wenn wir die Wurzel finden, wissen wir, dass es kein größerer Element als x gibt.

__Pseudocode__

find_next_largest(x):
    
    rc = x.right_child
    if rc:    
        return smallest_element_in(rc)
    else:
        while True:
            p = x.parent
            if !p:
                return "No greater element found"
            else if x < p:
                return p
            else if p < x:
                x = p
            else:
                return "Pls input search tree"

smallest_element_in(x):
    while True:
        lc = x.left_child
        if lc:
            x = lc
        else:
            return x

### b)

Knoten ohne Kinder bekommen den Wert 1. Knoten mit Kindern bekommen als Wert die Summe der Werte ihrer Kinder + 1. Wir benutzen rekursive Post Order Traversierung um den Baum von unten nach oben durchzugehen.

def count_children(BinTreeNode x):

    lc = x.left_child
    left_val = 0
    if (lc):
        left_val = count_children(lc)
    right_val = 0
    rc = x.right_child
    if (rc):
        right_val = count_children(rc)
    
    x.children_ctr = left_val + right_val + 1
    
    return x.children_ctr

## Aufgabe 4

### a)

        4
        
    3        6
    
1     5   7     !!

Die Anzahl an Knoten in einem 0-balancierten Binärbaum muss immer durch $\sum_{i = 0}^{n} 2^i$ (also 1, 3, 7, ...) angegeben werden können. Dies ist für 6 Knoten nicht möglich.

### b)

                    6.9
                6           7
            4     6+1/4         8
        3     5     6+1/π           9
    2
1

### c)

c=2

        x
    x
x

        x
    x
x     x

c=1

        x
    x      x
x

        x
    x      x
x            x

        x
    x      x
x     x

        x
    x      x
x     x      x