LINUX.ORG.RU

дерево двоичного поиска в ООП

 , ,


1

1

Я полагаю, вы знаете, что это такое. Как реализовать вставку элемента согласно оснопоопам (основным принципам ООП)?

Я думаю, надо объявить два класса «tip» и «node», которые наследованы от одного абстрактного класса «tree» или реализуют интерфейс «tree». Допустим, надо вставить элемент в дерево, а оно есть объект класса «tip». То есть метод объекта должен поменять класс этого объекта. Это возможно?


каст анонiмоус

anonymous
()

метод объекта должен поменять класс этого объекта

Нет.
Просто пусть твои классы, формирующие дерево, хранят указатель на элемент.

JacobTwoTwo
()

Надо объявить класс Pair c методами cons car и cdr (как в лиспе) и лепить из них linked list. Если постараться, наверное, можно и сам list сделать классом, но наверное это будет не особо тривиально.

numbershnumber
()

Класс Tree с различными методами и полем:

  • TreeNode Root;

Класс TreeNode c различными методами и полями:

  • TreeNode Left;
  • TreeNode Right;
  • TreeNode Parent;
  • <T> Data;
nihirash ★★★
()
Последнее исправление: nihirash (всего исправлений: 2)

поменять класс этого объекта. Это возможно?

А вообще, класс объекта поменять можно, только не во всех языках.

numbershnumber
()

Дичь какая то. Ты точно лекции не прогуливал? Понятные примеры иерархии классов были? Ну там про животных или геометрические фигуры?

redixin ★★★★
()

Займитесь другой профессией. Все эти abstract factory method push context provider с наследованием и 100500 слоями абстракции надоели.

dzidzitop ★★
()

Взять и реализовать. Блин, загугли лекции и почитай, обычно это в качестве примера приводят.

peregrine ★★★★★
()
Ответ на: комментарий от redixin

Понятные примеры иерархии классов были? Ну там про животных или геометрические фигуры?

В том-то и дело, что эти примеры относятся к философии, а не к программированию. 😉

beroal
() автор топика
Ответ на: комментарий от peregrine

Блин, загугли лекции и почитай

Я загуглил и почитал. Там нет связи с оснопоопами. Уточняю: меня интересует именно как это «правильно» делать в ООП.

beroal
() автор топика
Ответ на: комментарий от numbershnumber

Надо объявить класс Pair c методами cons car и cdr (как в лиспе) и лепить из них linked list. Если постараться, наверное, можно и сам lisp сделать, и наверное это будет особо тривиально.

//fixed

anonymous
()
Ответ на: комментарий от nihirash

Tree
TreeNode

Я не совсем понимаю. (Ссылка на родителя в данном контексте не нужна.) Tree просто хранит TreeNode?

beroal
() автор топика

Допустим, надо вставить элемент в дерево, а оно есть объект класса «tip».

В такой конструкции как у тебя, tip можно прицеплять только к node. Поэтому непонятно, в чём вопрос.

no-such-file ★★★★★
()
Последнее исправление: no-such-file (всего исправлений: 1)
Ответ на: комментарий от no-such-file

отдельно TreeLeaf с data.

data должна отвечать интерфейсу LeafableDataInterface.

nihirash ★★★
()
Ответ на: комментарий от beroal

Tree просто хранит TreeNode?

В классе Tree есть свои методы(такие как поиск вершины и т.д.), которые не относятся в вершине.

nihirash ★★★
()

BST можно представить в виде массива, если память не жмет то левый элемент будет 2i+1, правый 2i+2;

xpahos ★★★★★
()
Ответ на: комментарий от beroal

А делать узел подклассом дерева это из какой области?

redixin ★★★★
()

Посоветуйте ему книжку о структурах данных в C++ - я забыл автора.

SuoiCat
()

Не хватает пару фабрик и фасада.

urxvt ★★★★★
()

если так страждешь оснопоопам быть то покажи как ты мыслишь правильное ооп хэш

anonymous
()
Ответ на: комментарий от JacobTwoTwo

Просто пусть твои классы, формирующие дерево, хранят указатель на элемент.

Вы не могли бы написать пример кода? На любом япе. Слишком туманно.

beroal
() автор топика
Ответ на: комментарий от beroal

Что туманно? Что у тебя дерево? Связанный список скорее всего. Каждый элемент этого связанного списка содержит массив указателей на другие (подчинённые) узлы этого дерева. Так вот добавь туда ещё указатель на собственно полезные данные.
Ну или сядь и попробуй более внятно выразить свою мысль. Ктулху ногу сломит пока тебя поймёт.

JacobTwoTwo
()
public abstract class TreeNode<A> {

  interface Visitor<A>{
    public void visit(Tip<A> foo);
    public void visit(Bin<A> foo);
  }
  
  private TreeNode(){};

  abstract void accept(Visitor<A> v);

  public static final class Tip<A> extends TreeNode<A> {
    public String toString() {
      return "Tip";
    }
    public void accept(Visitor<A> v) {
      v.visit(this);
    }
  }

  public static final class Bin<A> extends TreeNode<A> {
    public final A data;
    public final TreeNode<A> left;
    public final TreeNode<A> right;

    public Bin(TreeNode<A> left, A data, TreeNode<A> right) {
       this.data = data;
       this.left = left;
       this.right = right;
    }

    public String toString() {
      return("Bin(" + this.left.toString() + "," + this.data.toString() + "," + this.right.toString()+")");
    }

    public void accept(Visitor<A> v) {
      v.visit(this);
    }
  }


  static abstract class Fold<A,B> implements Visitor<A> {
    private B seed;

    abstract B run(B seed, A value);

    public Fold(B initial, TreeNode<A> node) {
       this.seed = initial;
       node.accept(this);
    }

    public void visit(Tip<A> foo) {
    }

    public void visit(Bin<A> foo) {
      foo.left.accept(this);
      this.seed = run(this.seed, foo.data);
      foo.right.accept(this);
    }

    public B deconstruct() {
      return this.seed;
    }

  }

  public static void main(String[] args) {
    TreeNode<Integer> tip = new Tip<Integer>();
    TreeNode<Integer> a = new Bin<Integer>(tip, (Integer)5, new Bin<Integer>(tip,(Integer)7,tip));
    System.out.println(a);

    Fold<Integer, Integer> fold = new Fold<Integer,Integer>(0, a) {
       Integer run(Integer sum, Integer value) {
         return(sum +value);
       }
    };
    System.out.println(fold.deconstruct());

  }
}

не благодари, т.к. незачто.

qnikst ★★★★★
()
Последнее исправление: qnikst (всего исправлений: 1)
Ответ на: комментарий от qnikst

В чем разница между ними? Ну конкретно на Лоре аватарки разные, но это походу и все. Оба кокщика-хаскелиста с Украины

anonymous
()
Ответ на: комментарий от anonymous

не знаю в чем разница, но вроде иногда разные вещи писали.

qnikst ★★★★★
()
Ответ на: комментарий от redixin

Понятные примеры иерархии классов были? Ну там про животных или геометрические фигуры?

Про то, что в реальной жизни квадрат является прямоугольником, а в ООП эту иерархию не промоделируешь, не поломав принципов правильного дизайна?

utf8nowhere ★★★
()
Ответ на: комментарий от utf8nowhere

Т.е. нода подкласс дерева это правильный дизайн? Ясно понятно.

redixin ★★★★
()
Ответ на: комментарий от JacobTwoTwo

Что у тебя дерево? Связанный список скорее всего.

Не надо гадать. Лекции: —0—, —1—. Мой tip — это их nil или NULL. Не понятно, как NULL Си согласуется с принципами ООП. NULL — это объект или что?

beroal
() автор топика
Ответ на: комментарий от beroal

вот тебе без расширения классов вставка, но таким же образом можно и с расширенем сделать, даже проще выйдет. Функцию сравнения в класс тоже сам впихнуть можешь.

--- TreeNode.java.old	2017-08-21 15:09:02.402615265 +0300
+++ TreeNode.java	2017-08-21 15:27:01.435531144 +0300
@@ -20,8 +20,8 @@
 
   public static final class Bin<A> extends TreeNode<A> {
     public final A data;
-    public final TreeNode<A> left;
-    public final TreeNode<A> right;
+    public TreeNode<A> left;
+    public TreeNode<A> right;
 
     public Bin(TreeNode<A> left, A data, TreeNode<A> right) {
        this.data = data;
@@ -64,6 +64,35 @@
 
   }
 
+  static abstract class Insert<A> implements Visitor<A> {
+
+    private TreeNode<A> result; 
+    private A value;
+
+    public abstract int cmp(A value, A another);
+
+    public Insert(A value, TreeNode<A> node) {
+      this.value = value;
+      node.accept(this);
+    }
+
+    public void visit(Tip<A> foo) {
+      this.result = new Bin<A>(foo, this.value, foo);
+    }
+
+    public void visit(Bin<A> foo) {
qnikst ★★★★★
()
Ответ на: комментарий от nezamudich

дифф должен быть полным. можно и модифицированное старое сделать за +1 уровень индирекции. Держать TreeNode, в котором будет поле, которое модифицируется.

я на самом деле я сильно протупил, т.к. почему-то подумал, что до внутренней структуры пользователю есть какое-то дело, что очевидно не так. В другом случае когда бы сильно меньше было. Ну и вернуть хитрый итератор или сделать Foldable тоже бы было лучше, но уж очень вербозно, особенно когда под рукой нет ИДЕ.

qnikst ★★★★★
()
Ответ на: комментарий от nezamudich

согласен, мне вообще интересно было получится ли что-нибудь компилирующееся, а так я этот язык уже лет 10^W 7 не трогал.

qnikst ★★★★★
()
Ответ на: комментарий от nezamudich
--- TreeNode.java.old	2017-08-21 15:09:02.402615265 +0300
+++ TreeNode.java	2017-08-21 15:27:01.435531144 +0300
@@ -20,8 +20,8 @@
 
   public static final class Bin<A> extends TreeNode<A> {
     public final A data;
-    public final TreeNode<A> left;
-    public final TreeNode<A> right;
+    public TreeNode<A> left;
+    public TreeNode<A> right;
 
     public Bin(TreeNode<A> left, A data, TreeNode<A> right) {
        this.data = data;
@@ -64,6 +64,35 @@
 
   }
 
+  static abstract class Insert<A> implements Visitor<A> {
+
+    private TreeNode<A> result; 
+    private A value;
+
+    public abstract int cmp(A value, A another);
+
+    public Insert(A value, TreeNode<A> node) {
+      this.value = value;
+      node.accept(this);
+    }
+
+    public void visit(Tip<A> foo) {
+      this.result = new Bin<A>(foo, this.value, foo);
+    }
+
+    public void visit(Bin<A> foo) {
+      if (this.cmp(this.value, foo.data) <= 0) {
+        foo.left.accept(this);
+        foo.left = this.result;
+      } else {
+        foo.right.accept(this);
+        foo.right = this.result;
+      }
+      this.result = foo;
+    }
+
+  }
+
   public static void main(String[] args) {
     TreeNode<Integer> tip = new Tip<Integer>();
     TreeNode<Integer> a = new Bin<Integer>(tip, (Integer)5, new Bin<Integer>(tip,(Integer)7,tip));
@@ -76,6 +105,10 @@
     };
     System.out.println(fold.deconstruct());
 
+    new Insert<Integer>(8, a) { public int cmp(Integer a, Integer b) { return (a - b); } };
+    new Insert<Integer>(0, a) { public int cmp(Integer a, Integer b) { return (a - b); } };
+    System.out.println(a);
+
   }
 }
qnikst ★★★★★
()
Ответ на: комментарий от beroal

В том-то и дело, что эти примеры относятся к философии, а не к программированию.

Неплохой вборс, пойду попкорна куплю.

Dudraug ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.