TreeSet در جاوا

جاوا مجموعه وسیعی از ساختارهای داده را برای کار موثر با مجموعه عناصر فراهم می کند. یکی از این ساختارهای داده TreeSet است که پیاده‌سازی درخت قرمز-مشکی در جاوا است. TreeSet یک ترتیب مرتب شده برای ذخیره عناصر منحصر به فرد را حفظ می کند. ممکن است برای مبتدیان استفاده از کلاس Java TreeSet در ابتدا کمی چالش برانگیز باشد. در این مقاله، می‌خواهیم نحوه استفاده از TreeSet را بیابیم ، مفاهیم اصلی آن را توضیح دهیم و مثال‌هایی از کد ارائه کنیم تا به شما کمک کنیم تا TreeSet را در پروژه‌های جاوا خود وارد کنید.

ساختار TreeSet: درخت قرمز-سیاه

همانطور که قبلاً اشاره کردیم، ساختار کلاس Java TreeSet به عنوان درخت جستجوی باینری خود متعادل کننده به نام درخت قرمز-سیاه پیاده سازی می شود. بیایید توضیح دهیم که این چیست... درخت قرمز-سیاه یک ساختار داده جستجوی باینری متعادل را نشان می دهد که معمولاً برای ذخیره و سازماندهی داده های مرتب شده استفاده می شود. نام خود را از خواصی که تعادل آن را حفظ می کنند گرفته شده است:

• هر گره در درخت قرمز یا سیاه است.
• ریشه درخت سرخ سیاه همیشه سیاه است.
• تمام گره های برگ (گره های NIL یا پیوندهای پوچ) سیاه هستند.
• اگر یک گره از درخت قرمز باشد، فرزندان آن سیاه هستند.
• هر مسیر ساده از یک گره به گره های نواده آن شامل تعداد مساوی گره سیاه است.

درختان قرمز-سیاه عملکرد کارآمدی را برای عملیات درج، حذف و جستجوی عنصر با اطمینان از تعادل نشان می دهند. این تضمین می کند که ارتفاع درخت متناسب با لگاریتم تعداد گره های موجود در آن باقی می ماند و در نتیجه پیچیدگی زمانی لگاریتمی برای عملیات ایجاد می شود. درختان قرمز-سیاه کاربردهای گسترده ای در حوزه های مختلف پیدا می کنند، از جمله اجرای درخت های جستجوی متوازن در زبان های برنامه نویسی، پایگاه های داده (به عنوان مثال، ساختارهای شاخص داخلی)، و سناریوهای دیگر که در آن ذخیره سازی کارآمد و عملیات بر روی داده های مرتب شده ضروری است.

ویژگی ها و نقاط ضعف TreeSet

TreeSet چندین ویژگی کلیدی را ارائه می دهد که آن را به ابزاری ارزشمند برای مدیریت مجموعه ای از اشیاء به شیوه ای مرتب شده تبدیل می کند. مزایای:

• نگهداری خودکار عناصر به ترتیب مرتب شده. هنگام افزودن یا حذف عناصر، ساختار درختی تنظیم می شود تا آنها مرتب شوند. این کار نیاز به مرتب‌سازی دستی را از بین می‌برد و دسترسی کارآمد را به ترتیب صعودی یا نزولی فراهم می‌کند.
• عملیات جستجو، درج و حذف کارآمد. از یک ساختار درخت جستجوی دودویی استفاده می‌کند و این عملیات را با پیچیدگی زمانی O(log N) امکان‌پذیر می‌کند . در اینجا N تعداد عناصر است.
• TreeSet منحصر به فرد بودن عناصر را با استفاده از ترتیب طبیعی آنها یا مقایسه کننده سفارشی تضمین می کند . این هنگام کار با مجموعه هایی که به عناصر متمایز نیاز دارند مفید است.

محدودیت ها:

• به دلیل حفظ نظم مرتب شده ، کمی کندتر از HashSet .
• به عناصر تهی اجازه نمی دهد، زیرا برای مقایسه عناصر به ترتیب طبیعی یا یک مقایسه کننده سفارشی متکی است.

Java TreeSet: مثالی از عملیات اصلی

اکنون بیایید نحوه ایجاد یک TreeSet در جاوا را نشان دهیم، اندازه مجموعه را بدست آوریم، عناصر را به آن اضافه کنیم، آنها را حذف کنیم و بررسی کنیم که آیا یک عنصر در TreeSet وجود دارد یا خیر . این نمونه‌های کد عملیات اصلی را هنگام کار با TreeSet نشان می‌دهند : ایجاد یک نمونه، افزودن عناصر، حذف عناصر، بررسی وجود عنصر و به دست آوردن اندازه TreeSet . ایجاد یک نمونه TreeSet و افزودن عناصر:

// Creating a TreeSet of Integer type
TreeSet<Integer> numbers = new TreeSet<>();

// Adding elements to the TreeSet
numbers.add(18);
numbers.add(2);
numbers.add(7);
numbers.add(28);

System.out.println(numbers); // Output: [2, 7, 18, 28]

در اینجا از متد add() برای اضافه کردن 4 عدد در TreeSet استفاده می کنیم . اگر یک متد اصلی ایجاد کنیم و برنامه را اجرا کنیم، خروجی به ترتیب مرتب شده است (2، 7، 18، 28). حذف عناصر از TreeSet :

TreeSet<String> names = new TreeSet<>();

names.add("Johnny");
names.add("Ivy");
names.add("David");
names.add("Ricky");

// Removing an element from the TreeSet
names.remove("David");

System.out.println(names); // Output: [Ivy, Johnny, Ricky]

بررسی وجود یک عنصر در TreeSet :

TreeSet<String> musicalInstrument = new TreeSet<>();

musicalInstrument.add("Piano");
musicalInstrument.add("Drums");
musicalInstrumentfruits.add("Violin");
musicalInstrument.add("Double Bass");

// Checking if an element exists in the TreeSet
boolean containsPiano = musicalInstrument.contains("Piano");
boolean containsCello = musicalInstrument.contains("Cello");

System.out.println(containsPiano); // Output: true
System.out.println(containsCello); // Output: false

بدست آوردن اندازه TreeSet :

TreeSet<Character> letters = new TreeSet<>();

letters.add('A');
letters.add('B');
letters.add('C');
letters.add('D');

// Getting the size of the TreeSet
int size = letters.size();

System.out.println(size); // Output: 4

مرتب سازی و تکرار در TreeSet

TreeSet در جاوا ویژگی های قدرتمندی را برای مرتب سازی و تکرار بر روی مجموعه ای از عناصر فراهم می کند. در این بخش، تکنیک‌های مختلفی را برای مرتب‌سازی عناصر، تکرار در TreeSet و انجام جستجوهای مبتنی بر محدوده با استفاده از متدهای subSet() ، headSet() و tailSet() بررسی خواهیم کرد . به طور پیش فرض، TreeSet به طور خودکار عناصر را به ترتیب مرتب شده نگه می دارد. با این حال، می‌توانیم رفتار مرتب‌سازی را با ارائه یک مقایسه‌کننده در طول ایجاد TreeSet سفارشی کنیم . بیایید یک مثال را ببینیم:

import java.util.Comparator;
import java.util.TreeSet;

public class TreeSetSortingExample {
  public static void main(String[] args) {
    // Create a TreeSet with custom sorting
    TreeSet<Integer> numbers = new TreeSet<>(Comparator.reverseOrder());

    // Add elements to the TreeSet
    numbers.add(5);
    numbers.add(3);
    numbers.add(7);
    numbers.add(1);

    System.out.println(numbers); // Output: [7, 5, 3, 1]
  }
}

در کد بالا، یک TreeSet از نوع Integer ایجاد می کنیم و با استفاده از Comparator.reverseOrder() یک مقایسه کننده سفارشی برای مرتب کردن عناصر به ترتیب نزولی ارائه می کنیم. مجموعه درختی حاصل شامل عناصر [7، 5، 3، 1] خواهد بود . راه های متعددی برای تکرار روی TreeSet وجود دارد . ما می توانیم از یک تکرار کننده استفاده کنیم یا از حلقه تقویت شده برای هر استفاده کنیم . بیایید نمونه هایی از هر دو رویکرد را ببینیم:

import java.util.TreeSet;
import java.util.Iterator;

public class TreeSetIterationExample {
  public static void main(String[] args) {
    TreeSet<String> names = new TreeSet<>();

    names.add("Johnny");
    names.add("Ivy");
    names.add("Ricky");
    names.add("David");

    // Iterating using an iterator
    Iterator<String> iterator = names.iterator();
    while (iterator.hasNext()) {
      String name = iterator.next();
      System.out.println(name);
    }

    // Iterating using the enhanced for-each loop
    for (String name : names) {
      System.out.println(name);
    }
  }
}

در کد بالا یک TreeSet به نام names ایجاد می کنیم و چند عنصر اضافه می کنیم. سپس دو روش برای تکرار در TreeSet نشان می‌دهیم : استفاده از یک تکرارکننده و استفاده از حلقه تقویت‌شده برای هر. TreeSet روش هایی را برای انجام جستجوهای مبتنی بر محدوده ارائه می دهد که به ما امکان می دهد زیر مجموعه هایی از عناصر را بر اساس معیارهای خاص بازیابی کنیم. سه روش اصلی برای جستجوهای مبتنی بر محدوده عبارتند از:

• subSet(E fromElement، E toElement) : زیرمجموعه‌ای از عناصر را از fromElement (شامل) به toElement (انحصاری) برمی‌گرداند.
• headSet(E toElement) : زیر مجموعه ای از عناصر کمتر از toElement را برمی گرداند .
• tailSet(E fromElement) : زیر مجموعه ای از عناصر بزرگتر یا مساوی fromElement را برمی گرداند .

بیایید یک مثال را ببینیم:

import java.util.TreeSet;

public class TreeSetRangeSearchExample {
  public static void main(String[] args) {
    TreeSet<Integer> numbers = new TreeSet<>();

    numbers.add(1);
    numbers.add(3);
    numbers.add(5);
    numbers.add(7);
    numbers.add(9);

    // Performing range-based search using subSet()
    TreeSet<Integer> subset = new TreeSet<>(numbers.subSet(3, 8));
    System.out.println(subset); // Output: [3, 5, 7]

    // Performing range-based search using headSet()
    TreeSet<Integer> headSet = new TreeSet<>(numbers.headSet(6));
    System.out.println(headSet); // Output: [1, 3, 5]

    // Performing range-based search using tailSet()
     TreeSet<Integer> tailSet = new TreeSet<>(numbers.tailSet(5));
    System.out.println(tailSet); // Output: [5, 7, 9]
  }
}

در کد بالا یک TreeSet به نام اعداد ایجاد می کنیم و چند عنصر اضافه می کنیم. سپس جستجوهای مبتنی بر محدوده را با استفاده از متدهای subSet() ، headSet() و tailSet() نشان می دهیم .

• زیر مجموعه TreeSet شامل عناصری بین 3 (شامل) و 8 (انحصاری) است که [3، 5، 7] هستند .
• HeadSet TreeSet شامل عناصر کمتر از 6 است که عبارتند از [ 1، 3، 5] .
• tailSet TreeSet شامل عناصر بزرگتر یا مساوی 5 است که عبارتند از [5، 7 ، 9] .

این روش‌های جستجوی مبتنی بر محدوده به ما امکان می‌دهند تا زیر مجموعه‌هایی از عناصر را بر اساس معیارهای خاص بازیابی کنیم و در کار با داده‌های مرتب‌سازی شده انعطاف‌پذیری ایجاد کنیم.

مقایسه کننده در TreeSet: مرتب سازی با معیارهای سفارشی

به جز برای مرتب سازی طبیعی، می توانید از یک مقایسه کننده سفارشی برای مرتب سازی TreeSet استفاده کنید . در این بخش به مفهوم مقایسه کننده و نقش آن در TreeSet خواهیم پرداخت . ما چگونگی ایجاد یک TreeSet با مقایسه‌کننده سفارشی را بررسی خواهیم کرد و نمونه‌هایی از کد برای نشان دادن مرتب‌سازی TreeSet بر اساس معیارهای خاص ارائه می‌کنیم.

مقایسه کننده چیست؟

Comparator یک رابط در جاوا است که امکان مرتب سازی سفارشی اشیاء را فراهم می کند. این روشی را برای تعریف ترتیب عناصر بر اساس ویژگی ها یا ویژگی های خاص ارائه می دهد. با پیاده‌سازی رابط Comparator و نادیده گرفتن متد ()compare آن ، می‌توانیم نحوه مرتب‌سازی عناصر در یک TreeSet را مشخص کنیم .

ایجاد مجموعه درختی با مقایسه کننده سفارشی

برای ایجاد یک TreeSet با یک مقایسه کننده سفارشی، باید مقایسه کننده را به عنوان یک آرگومان در هنگام ایجاد نمونه TreeSet ارائه کنیم . بیایید یک مثال را ببینیم:

import java.util.Comparator;
import java.util.TreeSet;

public class TreeSetComparatorExample {
  public static void main(String[] args) {
    // Create a TreeSet with a custom comparator
    TreeSet<String> names = new TreeSet<>(new LengthComparator());

    // Add elements to the TreeSet
    names.add("Johnny");
    names.add("Ivy");
    names.add("Rick");
    names.add("David");

    System.out.println(names); // Output: [Ivy, Johnny, David, Rick]
  }
}

class LengthComparator implements Comparator<String> {
  @Override
  public int compare(String s1, String s2) {
    return Integer.compare(s1.length(), s2.length());
  }
}

در کد بالا، یک TreeSet به نام names با یک مقایسه کننده سفارشی به نام LengthComparator ایجاد می کنیم . LengthComparator طول دو رشته را مقایسه می کند و آنها را بر اساس آن مرتب می کند . در نتیجه، TreeSet بر اساس طول رشته ها مرتب می شود و خروجی [Ivy, Rick, David, Johnny] را به ما می دهد .

نمونه هایی از مرتب سازی TreeSet با استفاده از مقایسه کننده

علاوه بر ایجاد یک TreeSet با یک مقایسه کننده سفارشی، ما همچنین می توانیم از یک مقایسه کننده برای مرتب کردن یک TreeSet به طور موقت بدون تغییر ترتیب طبیعی آن استفاده کنیم. بیایید یک مثال را ببینیم:

import java.util.Comparator;
import java.util.TreeSet;

  public class TreeSetTest {
    public static void main(String[] args) {
      TreeSet<String> names = new TreeSet<>();

      names.add("Johnny");
      names.add("Ivy");
      names.add("Ricky");
      names.add("David");

      // Sort TreeSet temporarily using a comparator
      TreeSet<String> sortedNames = new TreeSet<>(Comparator.reverseOrder());
      sortedNames.addAll(names);

      System.out.println(sortedNames); // Output: [Ricky, Johnny, Ivy, David]
      System.out.println(names); // Output: [David, Ivy, Johnny, Ricky]
    }
  }

در کد بالا یک TreeSet به نام names ایجاد می کنیم و چند عنصر اضافه می کنیم. سپس یک TreeSet جدید به نام sortedNames با یک مقایسه کننده سفارشی () Comparator.reverseOrder ایجاد می کنیم . با افزودن تمام عناصر از نام های اصلی TreeSet به SortedNames ، نسخه مرتب شده موقتی از TreeSet را به دست می آوریم .

مقایسه TreeSet با سایر ساختارهای داده

مقایسه TreeSet با HashSet

هر دو TreeSet و HashSet پیاده سازی رابط Set در جاوا هستند . با این حال، تفاوت های قابل توجهی بین آنها وجود دارد. TreeSet : TreeSet عناصر منحصر به فرد را به ترتیب مرتب شده ذخیره می کند. از درخت جستجوی دودویی خود متعادل کننده (معمولاً درخت قرمز-سیاه) برای حفظ ترتیب مرتب شده استفاده می کند که در نتیجه پیچیدگی زمانی لگاریتمی برای عملیات هایی مانند درج، حذف و جستجو ایجاد می شود. TreeSet برای نگهداری یک مجموعه مرتب شده و انجام عملیات مبتنی بر محدوده کارآمد است. با این حال، به دلیل ساختار درختی، سربار حافظه بالاتری دارد و اجازه عناصر تهی را نمی دهد. HashSet : HashSet عناصر منحصر به فرد را به صورت نامرتب و با استفاده از کدهای هش و قابلیت hashtable به صورت داخلی ذخیره می کند. این پیچیدگی زمانی ثابت را برای عملیات اساسی مانند درج، حذف و جستجو فراهم می کند. HashSet برای جستجوی سریع عناصر کارآمد است و هیچ سربار حافظه اضافی برای حفظ نظم تحمیل نمی کند. با این حال، هیچ ترتیب خاصی از عناصر را تضمین نمی کند.

زمان استفاده از TreeSet:

• زمانی که نیاز دارید عناصر را به صورت خودکار مرتب کنید.
• زمانی که به عملیات مبتنی بر محدوده نیاز دارید یا نیاز به یافتن عناصر در یک محدوده خاص به طور موثر دارید.
• زمانی که عناصر تکراری مجاز نیستند و منحصر به فرد بودن ضروری است.
• زمانی که مایلید استفاده از حافظه کمی بالاتر را با مزایای عملیات مرتب‌سازی خودکار و محدوده جایگزین کنید.

مقایسه TreeSet با ArrayList

ArrayList یک پیاده سازی آرایه پویا در جاوا است. در اینجا تفاوت های اصلی بین TreeSet و ArrayList وجود دارد :

• TreeSet : TreeSet عناصر منحصر به فرد را به ترتیب مرتب شده ذخیره می کند و عملیات کارآمد را برای حفظ مجموعه مرتب شده و انجام جستجوهای مبتنی بر محدوده ارائه می دهد. دارای پیچیدگی زمانی لگاریتمی برای عملیات است. TreeSet برای دسترسی تصادفی یا حفظ ترتیب درج مناسب نیست.
• ArrayList : ArrayList عناصر را به ترتیب درج ذخیره می‌کند و با استفاده از شاخص‌ها، دسترسی سریع تصادفی به عناصر را فراهم می‌کند. این پیچیدگی زمانی ثابت برای اکثر عملیات هنگام دسترسی به عناصر بر اساس شاخص دارد. با این حال، پیچیدگی زمانی خطی برای درج یا حذف عناصر از وسط لیست دارد، زیرا نیاز به تغییر عناصر دارد.

چه زمانی باید سایر ساختارهای داده را در نظر گرفت

• اگر نگهداری عناصر به ترتیب مرتب شده مورد نیاز نیست، و به جستجوی سریع عناصر یا یک مجموعه نامرتب نیاز دارید، HashSet ممکن است انتخاب بهتری باشد.
• اگر به دسترسی تصادفی مکرر به عناصر بر اساس فهرست نیاز دارید یا نیاز به حفظ ترتیب درج دارید، ArrayList مناسب تر خواهد بود.