Binary Tree vs Binary Search Baum Big Oh Analysis

Question

Würde ein ausgewogener binärer Suchbaum Ihnen helfen, die folgende Aufgabe in einer schnelleren Big-Oh-Zeit als ein ausgewogener Binärbaum zu erfüllen?

Erstellen einer Liste aller Elemente in dem Baum, der kleiner ist als ein Wert v.

Meiner Meinung nach nicht, denn was, wenn alle Werte in der BST sind kleiner als v. Dann würden Sie jedem Besuch müssen Knoten und das wäre O (n), die nicht besser als ein binärer Baum ist.

Bin ich richtig?

Answer 1

Meiner Meinung nach nicht, denn was, wenn alle Werte in der BST sind kleiner als v. Dann würden Sie jeden Knoten besuchen müssen, und das wäre O (n) sein, die nicht besser als ein binäres ist Baum.

Bin ich richtig?

Sie sind. Beachten Sie jedoch, dass für alle praktischen Zwecke ist besser, BST zu verwenden, da mit "plain" binären Baum Sie immer haben, alle Knoten zu besuchen, um diejenigen kleiner als v zu finden, während in BST mit In-Order-Traversal untersuchen Sie nur diese kleiner als v.