TreeSet

کلاس TreeSet زیر کلاس AbstractSet است و مفهوم Set یعنی یک مجموعه بدون تکرار را پیاده سازی می کند ، قبلاً با مفهوم Set آشنا شدیم ، کلاس TreeSet از ساختمان داده درخت موازنه برای نگه داری اعضای مجموعه استفاده می کند ، لذا اعضای این مجموعه به صورت مرتب نگه داری می شوند و عملیات درج ، حذف ، جست و جو در زمان کوتاهی (زمان لگاریتمی) صورت می پذیرد.

اشیای داخل TreeSet به صورت پیش فرض بر اساس ترتیب الفبایی مرتب هستند مگر آنکه در سازنده آن صریحاً از یک Comparator اختصاصی استفاده کنیم.مهم ترین ویژگی های TreeSet عبارتند از :

به دلیل بهینه بودن TreeSet از آن در الگوریتم های پیشرفته ای همچون الگوریتم های مسیر یابی استفاده می شود.از طریق مسیر java.util.TreeSet می توانیم به این کلاس دسترسی داشته باشیم.برای ساخت شی جدید از TreeSet می توانیم از یکی از سازنده های زیر استفاده کنیم :

TreeSet()

یک TreeSetخالی ایجاد می کند.

TreeSet(Collection c)

یک TreeSet ایجاد می کند و اعضای کالکشن c را به آن اضافه می کند.

TreeSet(Comparator cmp)

از cmp برای مقایسه و مرتب سازی اعضا استفاده می کند.

TreeSet(SortedSet ss)

یک TreeSetجدید ایجاد کرده و اعضای ss را به آن اضافه می کند به علاوه ترتیب اعضا را نیز به همان شکل قبلی نگه می دارد.متد های مهم TreeSet در جدول زیر آمده اند :

متد کاربرد
boolean add(Object o) یک عضو جدید به مجموعه اضافه می کند.
boolean addAll(Collection c) اعضای یک کالکشن دیگر را به مجموعه اضافه می کند.
Object ceiling(Object o) عضوی از مجموعه که از شی o بزرگتر یا مساوی باشد را بر می گرداند ، اگر چنین شی ای وجود نداشته باشد خروجی null خواهد بود.
void clear() کل مجموعه را پاک می کند.
Comparator comparator() Comparator مجموعه را بر می گرداند ، اگر از ترتیب طبیعی استفاده شده باشد خروجی null خواهد بود.
boolean contains(Object o) وجود یا عدم وجود یک شی در مجموعه را بررسی می کند.
Iterator descendingIterator() یک Iterator معکوس در اختیار ما قرار می دهد که می توانیم مجموعه را از انتها به ابتدا پیمایش کنیم.
NavigableSet descendingSet() معکوس مجموعه فعلی را در اختیار ما قرار می دهد.
Object first() عضو ابتدایی (کوچکترین عضو) مجموعه را بر می گرداند.
Object floor(Object o) عضوی از مجموعه که از شی o کوچکتر یا مساوی باشد را بر می گرداند ، اگر چنین موردی وجود نداشته باشد خروجی null خواهد بود.
SortedSet headSet(Object to) زیر مجموعه ای را بر می گرداند که اعضای آن از to کوچکتر باشند.
NavigableSet headSet(Object to,boolean include) مانند متد قبلی است با این تفاوت که پارامتر دوم مشخص می کند که اشیا منحصراً از to کوچکتر باشند یا کوچکتر مساوی؟
Object higher(Object o) شی ای از مجموعه را بر می گرداند که از o بزرگتر باشد.
boolean isEmpty() خالی بودن مجموعه را بررسی می کند.
Iterator iterator() یک Iterator برای پیمایش ابتدا تا انتهای لیست در اختیار ما قرار می دهد.
Object last() آخرین (بزرگترین) عضو مجموعه را بر می گرداند.
Object lower(Object o) عضوی از مجموعه که از شی O کوچکتر باشد را بر می گرداند.
Object pollFirst() عضو ابتدایی (کوچکترین عضو) را از مجموعه حذف می کند.
Object pollLast() عضو انتهایی (بزرگترین عضو) را از مجموعه حذف می کند.
boolean remove(Object o) شی مورد نظر را از مجموعه حذف می کند.
int size() اندازه مجموعه را بر می گرداند.
NavigableSet subSet(Object from,boolean fi,Object to,boolean ti) یک زیر مجموعه که اعضای آن از from بزرگتر و از to کوچکتر باشند بر می گرداند.پارامتر های ti و fi تعیین می کنند که اعضای مساوی با toو from نیز در زیر مجموعه قرار گیرند یا خیر؟
SortedSet subSet(Object from,Object to) یک زیر مجموعه که اعضای آن از from بزرگتر-مساوی و از to کوچکتر باشند بر می گرداند.
SortedSet tailSet(Object from) یک زیر مجموعه بر می گرداند که اعضای آن از from بزرگتر باشند.
NavigableSet tailSet(Object from,boolean include) یک زیر مجموعه بر می گرداند که اعضای آن از from بزرگتر باشند.پارامتر دوم مشخص می کند که اشیا از from بزرگتر باشند یا بزرگتر مساوی؟

در ادامه با چند مثال با TreeSet بیشتر آشنا می شویم.در مثال زیر یک TreeSet ساده ایجاد می کنیم و چند متد بسیار مهم آن را مورد بررسی قرار می دهیم.

import java.util.TreeSet;
public class TreeSetDemo 
{
    public static void main(String[] args) 
    {
        TreeSet treeset = new TreeSet();

        treeset.add(5);
        treeset.add(1);
        treeset.add(4);
        treeset.add(9);
        treeset.add(1);
        treeset.add(6);
        treeset.add(5);

        System.out.println(treeset);

        //first and last
        System.out.println(treeset.first());
        System.out.println(treeset.last());

        //higher
        System.out.println(">5 :" + treeset.higher(5));
        System.out.println(">8 :" + treeset.higher(8));

        //ceiling
        System.out.println(">=5 :" + treeset.ceiling(5));
        System.out.println(">=8 :" + treeset.ceiling(8));

        //lower
        System.out.println("<5 :" + treeset.lower(5));
        System.out.println("<8 :" + treeset.lower(8));

        //floor
        System.out.println("<=5 :" + treeset.floor(5));
        System.out.println("<=8 :" + treeset.floor(8));
    }
}

[1, 4, 5, 6, 9]
1
9
>5 :6
>8 :9
>=5 :5
>=8 :9
<5 :4
<8 :6
<=5 :5
<=8 :6

در کد بالا ابتدا یک TreeSet ایجاد می کنیم و سپس اعدادی را با استفاده از متد add به آن اضافه می کنیم و سپس مجموعه را چاپ می کنیم مشاهده می کنیم که مجموعه دارای عضو تکراری نیست و به صورت مرتب نگه داری می شود. پس از آن با استفاده از متد های first و last اعضای ابتدایی (کوچکترین) و انتهایی (بزرگترین) مجموعه را چاپ می کنیم. سپس متد higher را مورد بررسی قرار می دهیم ، مشاهده می کنیم که این متد عضوی را بر می گرداند که حتماً از شی مورد نظر بزرگتر باشد. سپس متد ceiling را مورد بررسی قرار می دهیم ، مشاهده می کنیم که این متد عضوی را بر می گرداند که بزرگتر یا مساوی با شی مورد نظر باشد. سپس متد lower را مورد بررسی قرار می دهیم ، مشاهده می کنیم که این متد عضوی را بر می گرداند که حتماً از شی مورد نظر کوچکتر باشد. سپس متد floor را مورد بررسی قرار می دهیم ، مشاهده می کنیم که این متد عضوی را بر می گرداند که کوچکتر یا مساوی با شی مورد نظر باشد.

import java.util.TreeSet;

public class TreeSetDemo 
{
    public static void main(String[] args) 
    {
        TreeSet treeset = new TreeSet();

        treeset.add(5);
        treeset.add(1);
        treeset.add(4);
        treeset.add(9);
        treeset.add(8);
        treeset.add(6);
        treeset.add(5);

        System.out.println(treeset);

        System.out.println(treeset.subSet(4, 8));

        System.out.println(treeset.pollFirst());
        System.out.println(treeset.pollLast());
        System.out.println(treeset);

        System.out.println(treeset.descendingSet());
    }
}

[1, 4, 5, 6, 8, 9]
[4, 5, 6]
1
9
[4, 5, 6, 8]
[8, 6, 5, 4]

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