Tekrarlanan değerlere ve ikili karşılaştırmaya sahip bir AVL ağacı

Question 1

İki değeri olan nesnelerin bir veri yapısını (çoğunlukla AVL ağaçlarını kullanarak) oluşturmam gerekiyor: seviye (benzersiz değil) ve kimlik (benzersiz).

Kimlik, baskı arayarak seviyeleri sırası ile destek için, böyle iki ağaç birleştirme gibi korumak ve bu fonksiyonlar yeni ağaç ihtiyacım var.

Aklımda zaten birkaç çözüm var ama belirli bir çözüm hakkında soru sormak istedim:

Bu yapıyı, iki düğümün önce seviyelerine ve sonra kimliklerine göre karşılaştırıldığı tekil bir AVL ağacıyla uygulamak işe yarayacak mı? Çoğunlukla, bu tür iki ağacın birleştirilmesinin nasıl işe yarayabileceğini anlamaya çalışıyorum, özellikle de tüm nesnelerin x seviyesinde olduğu A ağacımız ve tüm nesnelerin y seviyesinde olduğu B ağacımız varsa.

DÜZENLEME: Ayrıca kimliği aramak için ek olarak yalnızca kimliğe göre sıralanmış bir ağaç olacaktır.

Bu yöntem işe yarar mı?

Question 2

iki düğümün önce seviyelerine ve sonra kimliklerine göre karşılaştırıldığı tekil AVL ağacı?

Yok ne yazık ki. Bunu yaparsanız, bir düğümü kimliğine göre verimli bir şekilde bulamazsınız-belirtmediğiniz tüm olası 'seviyelere' bakmanız gerekir, bu yüzden sınırsız olabileceğini varsayıyorum.

Bunun yerine, her düğümü iki ayrı AVL ağacına eklemek isteyebilirsiniz. Bir AVL ağacı düğümleri seviyeye göre, diğeri kimliklerine göre sıralayacaktır. Tüm sorgular, eklemeler, silmeler ve birleştirmeler her ağaçta ayrı ayrı yapılabilir.

Başka bir deyişle, verileriniz üzerinde iki dizin oluşturursunuz.

Kodda:

struct Node {
    int id;
    int level;

    // by id
    int id_bf;
    Node *id_left, *id_right;

    // by level
    int level_bf;
    Node *level_left, *level_right;
};

DÜZENLEME: Ayrıca kimliği aramak için ek olarak yalnızca kimliğe göre sıralanmış bir ağaç olacaktır.

O zaman aslında benimle aynı şeyi tarif ediyorsun. Ancak, kompozite göre sıralanmış ağacınız (level, id) anahtar israftır; ihtiyacınız olan tek şey sıralanmış bir ağaçtır (level) ve sıralanmış bir ağaç (id) (skaler tuşlar). Sağladığınız işlemler arasında sıralamaya gerek yoktur (level, id) ve (id).

Yakov Galka · Answer 1 · 2021-11-23T19:29:44

iki düğümün önce seviyelerine ve sonra kimliklerine göre karşılaştırıldığı tekil AVL ağacı?

Yok ne yazık ki. Bunu yaparsanız, bir düğümü kimliğine göre verimli bir şekilde bulamazsınız-belirtmediğiniz tüm olası 'seviyelere' bakmanız gerekir, bu yüzden sınırsız olabileceğini varsayıyorum.

Bunun yerine, her düğümü iki ayrı AVL ağacına eklemek isteyebilirsiniz. Bir AVL ağacı düğümleri seviyeye göre, diğeri kimliklerine göre sıralayacaktır. Tüm sorgular, eklemeler, silmeler ve birleştirmeler her ağaçta ayrı ayrı yapılabilir.

Başka bir deyişle, verileriniz üzerinde iki dizin oluşturursunuz.

Kodda:

struct Node {
    int id;
    int level;

    // by id
    int id_bf;
    Node *id_left, *id_right;

    // by level
    int level_bf;
    Node *level_left, *level_right;
};

DÜZENLEME: Ayrıca kimliği aramak için ek olarak yalnızca kimliğe göre sıralanmış bir ağaç olacaktır.

O zaman aslında benimle aynı şeyi tarif ediyorsun. Ancak, kompozite göre sıralanmış ağacınız (level, id) anahtar israftır; ihtiyacınız olan tek şey sıralanmış bir ağaçtır (level) ve sıralanmış bir ağaç (id) (skaler tuşlar). Sağladığınız işlemler arasında sıralamaya gerek yoktur (level, id) ve (id).

Cevap için teşekkürler ne yazık ki, ek olarak bu işlevsellik için kimliğe göre sıralanmış bir ağaca sahip olacağımı söylemeyi unuttum. Seni düşündüm çözüm Sadece bir sınıf arkadaşının bana söylediği bu çözümü merak ediyordum ki birleştirme yüzünden işe yaramayacağını düşünüyorum,
@user3917631: (düzey, kimlik) 'e göre sıralanmış bir ağaç da (düzey)' e göre sıralanır. Bu nedenle, bunlardan herhangi birine ek olarak (kimliğe) göre sıralanmış bir ağacınız varsa, işlemleri tarif ettiğim gibi verimli bir şekilde yapabileceksiniz. İhtiyacınız olan tek şey (seviye) ise (seviye, kimlik) ile sıralamak biraz israftır.
Biliyorum, sadece ilgimi çekmeden soruyorum, işe yarayabilir mi? Her iki tamsayıya göre (seviye, kimlik) sıralanmış iki ağacın olması ve bunları O(n) (n birleştirilmiş düğüm sayısı) içinde birleştirmesi mümkün mü?
@user3917631: evet mümkündür ve başka bir şeye göre sıralanmış iki ağacı birleştirmekten farklı değildir. İkili arama ağaçları karşılaştırmaya dayanır, bu nedenle tamamen sıralı bir set olduğu sürece anahtarınız için ne kullandığınızı' umursamazlar'. Tamsayılar kümesi kümesidir. AVL ağaçlarıyla ilgili Wikipedia makalesi, verimli birleştirmenin nasıl yapılacağını açıklar; buna birlik denir. Bununla birlikte, bunu yapmak için bir denge faktörü yerine düğüm yüksekliğini saklamak isteyebilirsiniz.

Tekrarlanan değerlere ve ikili karşılaştırmaya sahip bir AVL ağacı

Soru

En iyi cevabı

Diğer dillerde

Bu sayfa diğer dillerde

Bu kategoride popüler

Popüler soruları bu kategoride