Java-BST auf der Suche für den maximalen Wert werden die meisten effizient

Lange Zeit Leser, erste mal poster (vor allem, weil 99% aller Fragen bereits beantwortet wurden, hier!!!)

Ich habe das surfen für über eine Stunde und ich bin nicht in der Lage, eine Lösung zu finden für dieses problem. Angesichts einer pre-sortiert ausgewogene binären Suchbaum, ich bin beauftragt, mit der folgende Methode, um den max-Wert in der Struktur effizienter:

private int max(IntTreeNode root) {
    if (root.left == null && root.right == null)
        return root.data;
    else {
        int maxValue = root.data;
        if (root.left != null)
            maxValue=Math.max(maxValue,max(root.left));
        if (root.right != null)
            maxValue = Math.max(maxValue,max(root.right));
        return maxValue;

Hier meine 2 Gedanken (und wahrscheinlich einer von Ihnen ist falsch und das ist das problem):

1), Während er sortiert und ausgewogen, es können in der Größe variieren, deshalb habe ich die überprüfen jedes und jedes Blatt, weil der einzige parameter der Methode ist ein root sehe ich keine Verknüpfung gibt.

2) die Gleiche Ursache sein, einzelne parameter, das heißt ich habe die Linie maxwert=Math.max(maxwert,max(Wurzel.Links)); in jedem rekursiven Aufruf um eine laufende Nummer auf maxValue. So sehe ich nicht, wo überspringen Sie diese nutzlosen Berechnungen.

Die Frage ist, wie würden Sie die Methode effizienter gegeben, die sortiert ausgewogene BST information, die andere information ist nur, wo ich bin auf Sie alle. Dank

Bearbeiten
Ich glaube, ich war besorgt über eine 11-element-Baum

         1
       /   \
      2      3
     / \    /  \
    4  5    6    7
   / \/\  /  \ / \  (making a tree got real hard)
  8  9 10 11        (this row is a little messed up but demonstrates the point)

Punkt ist, wenn man nur die rechten, Sie werden am Ende bei 7, und somit falsch sein. Es sei denn, ich bin verwirrt über die Bedeutung sortiert BST, tun BST ' s immer voll auf der unteren Reihe?

Da der Baum ist sortiert, der max Wert sollte an der rechten Kante, so dass keine Notwendigkeit, um zu überprüfen, root.Links.
Was haben Sie dargestellt ist nur ein binary tree. Binary search Tree (BST) ist ein Spezialfall von Binär-Baum. en.wikipedia.org/wiki/Binary_search_tree
Okay, gut, dass wenigstens Sinn macht, ty Ajai! Diese Art von Baum ist das, was die Programm-Ausgänge, die wir erhielten, und die Aufgabe lautet: "schreiben Sie die min-und max-Methoden, so dass Sie arbeiten mit einer Binären Suche Baum. Fügen Sie diese Methoden, um den code, den wir arbeiteten wir während der Unterrichtszeit. Die Methoden sollten den Umstand nutzen, dass der Baum sortiert ist und sollte nicht untersuchen Knoten, wenn nötig." Also ich weiß nicht understandwhy die Zuordnung ist unabhängig von der bereitgestellten Quellcode lol, aber bei Ihrem link und die Informationen der rechten Seite nur Baum-option macht Sinn, ty an alle

InformationsquelleAutor Danny Randolph | 2013-12-12

  1. 2

    In ein BST die am weitesten rechts element ist das maximum.

    Hier ist der pseudocode.

    int getMax(Node root) { //check if root is null
   if(root.right == null) {
       return root.data 
   } else {
       return getMax(root.right)
   }
}

    Für eine ausgewogene Struktur, Ordnung, wäre O(log n).

    InformationsquelleAutor 4J41

  2. 0

    für die LHS es immer kleiner als die Wurzel, so dass keine Notwendigkeit zu suchen, verwenden Sie dieses :

    private int max(IntTreeNode root) {
     if ( root.right == null) //no need to search in LHS
       return root.data;
     else {
        int maxValue = root.data;
        maxValue = Math.max(maxValue,max(root.right));
     }
     return maxValue;

    wenn dies nicht, Sie wollen fragte mich erneut, was Sie wollen, ist Ihre erwartete Ausgabe von dieser Methode, und ich werde versuchen, Ihnen zu helfen 🙂

    InformationsquelleAutor Khalid Abu El-Soud

Schreibe einen Kommentar