Bagikan melalui

Kelas CRBTree

  • Artikel

Kelas ini menyediakan metode untuk membuat dan memanfaatkan pohon Merah-Hitam.

Sintaks

template <typename K,
          typename V,
          class KTraits = CElementTraits<K>,
          class VTraits = CElementTraits<V>>
class CRBTree

Parameter

K
Jenis elemen kunci.

V
Jenis elemen nilai.

KTraits
Kode yang digunakan untuk menyalin atau memindahkan elemen kunci. Lihat Kelas CElementTraits untuk detail selengkapnya.

VTraits
Kode yang digunakan untuk menyalin atau memindahkan elemen nilai.

Anggota

Typedef Publik

Nama Deskripsi
CRBTree::KINARGTYPE Jenis yang digunakan saat kunci diteruskan sebagai argumen input.
CRBTree::KOUTARGTYPE Jenis yang digunakan saat kunci dikembalikan sebagai argumen output.
CRBTree::VINARGTYPE Jenis yang digunakan saat nilai diteruskan sebagai argumen input.
CRBTree::VOUTARGTYPE Jenis yang digunakan saat nilai diteruskan sebagai argumen output.

Kelas Publik

Nama Deskripsi
CRBTree::Kelas CPair Kelas yang berisi elemen kunci dan nilai.

Konstruktor Publik

Nama Deskripsi
CRBTree::~CRBTree Destruktor.

Metode Publik

Nama Deskripsi
CRBTree::FindFirstKeyAfter Panggil metode ini untuk menemukan posisi elemen yang menggunakan kunci berikutnya yang tersedia.
CRBTree::GetAt Panggil metode ini untuk mendapatkan elemen pada posisi tertentu di pohon.
CRBTree::GetCount Panggil metode ini untuk mendapatkan jumlah elemen di pohon.
CRBTree::GetHeadPosition Panggil metode ini untuk mendapatkan nilai posisi untuk elemen di kepala pohon.
CRBTree::GetKeyAt Panggil metode ini untuk mendapatkan kunci dari posisi tertentu di pohon.
CRBTree::GetNext Panggil metode ini untuk mendapatkan penunjuk ke elemen yang disimpan dalam CRBTree objek, dan lanjutkan posisi ke elemen berikutnya.
CRBTree::GetNextAssoc Panggil metode ini untuk mendapatkan kunci dan nilai elemen yang disimpan di peta dan lanjutkan posisi ke elemen berikutnya.
CRBTree::GetNextKey Panggil metode ini untuk mendapatkan kunci elemen yang disimpan di pohon dan lanjutkan posisi ke elemen berikutnya.
CRBTree::GetNextValue Panggil metode ini untuk mendapatkan nilai elemen yang disimpan di pohon dan lanjutkan posisi ke elemen berikutnya.
CRBTree::GetPrev Panggil metode ini untuk mendapatkan penunjuk ke elemen yang disimpan dalam CRBTree objek, lalu perbarui posisi ke elemen sebelumnya.
CRBTree::GetTailPosition Panggil metode ini untuk mendapatkan nilai posisi untuk elemen di ekor pohon.
CRBTree::GetValueAt Panggil metode ini untuk mengambil nilai yang disimpan pada posisi tertentu dalam CRBTree objek.
CRBTree::IsEmpty Panggil metode ini untuk menguji objek pohon kosong.
CRBTree::RemoveAll Panggil metode ini untuk menghapus semua elemen dari CRBTree objek.
CRBTree::RemoveAt Panggil metode ini untuk menghapus elemen pada posisi yang diberikan dalam CRBTree objek.
CRBTree::SetValueAt Panggil metode ini untuk mengubah nilai yang disimpan pada posisi tertentu dalam CRBTree objek.

Keterangan

Pohon Merah-Hitam adalah pohon pencarian biner yang menggunakan sedikit informasi tambahan per simpul untuk memastikan bahwa pohon tersebut tetap "seimbang," yaitu, tinggi pohon tidak tumbuh secara tidak proporsional besar dan memengaruhi performa.

Kelas templat ini dirancang untuk digunakan oleh CRBMap dan CRBMultiMap. Sebagian besar metode yang membentuk kelas turunan ini disediakan oleh CRBTree.

Untuk diskusi yang lebih lengkap tentang berbagai kelas koleksi dan fitur serta karakteristik performanya, lihat Kelas Koleksi ATL.

Persyaratan

Header: atlcoll.h

CRBTree::Kelas CPair

Kelas yang berisi elemen kunci dan nilai.

class CPair : public __POSITION

Keterangan

Kelas ini digunakan oleh metode CRBTree::GetAt, CRBTree::GetNext, dan CRBTree::GetPrev untuk mengakses elemen kunci dan nilai yang disimpan dalam struktur pohon.

Anggotanya adalah sebagai berikut:

Anggota data Deskripsi
m_key Anggota data yang menyimpan elemen kunci.
m_value Anggota data yang menyimpan elemen nilai.

CRBTree::~CRBTree

Destruktor.

~CRBTree() throw();

Keterangan

Membebaskan sumber daya yang dialokasikan. Memanggil CRBTree::RemoveAll untuk menghapus semua elemen.

CRBTree::FindFirstKeyAfter

Panggil metode ini untuk menemukan posisi elemen yang menggunakan kunci berikutnya yang tersedia.

POSITION FindFirstKeyAfter(KINARGTYPE key) const throw();

Parameter

kunci
Nilai kunci.

Tampilkan Nilai

Mengembalikan nilai posisi elemen yang menggunakan kunci berikutnya yang tersedia. Jika tidak ada elemen lagi, NULL dikembalikan.

Keterangan

Metode ini memudahkan untuk melintasi pohon tanpa harus menghitung nilai posisi sebelumnya.

CRBTree::GetAt

Panggil metode ini untuk mendapatkan elemen pada posisi tertentu di pohon.

CPair* GetAt(POSITION pos) throw();
const CPair* GetAt(POSITION pos) const throw();
void GetAt(POSITION pos, KOUTARGTYPE key, VOUTARGTYPE value) const;

Parameter

pos
Nilai posisi.

kunci
Variabel yang menerima kunci.

value
Variabel yang menerima nilai .

Tampilkan Nilai

Dua formulir pertama mengembalikan penunjuk ke CPair. Formulir ketiga memperoleh kunci dan nilai untuk posisi yang diberikan.

Keterangan

Nilai posisi sebelumnya dapat ditentukan dengan panggilan ke metode seperti CRBTree::GetHeadPosition atau CRBTree::GetTailPosition.

Dalam build debug, kegagalan pernyataan akan terjadi jika pos sama dengan NULL.

CRBTree::GetCount

Panggil metode ini untuk mendapatkan jumlah elemen di pohon.

size_t GetCount() const throw();

Tampilkan Nilai

Mengembalikan jumlah elemen (setiap pasangan kunci/nilai adalah satu elemen) yang disimpan di pohon.

CRBTree::GetHeadPosition

Panggil metode ini untuk mendapatkan nilai posisi untuk elemen di kepala pohon.

POSITION GetHeadPosition() const throw();

Tampilkan Nilai

Mengembalikan nilai posisi untuk elemen di kepala pohon.

Keterangan

Nilai yang dikembalikan oleh GetHeadPosition dapat digunakan dengan metode seperti CRBTree::GetKeyAt atau CRBTree::GetNext untuk melintasi pohon dan mengambil nilai.

CRBTree::GetKeyAt

Panggil metode ini untuk mendapatkan kunci dari posisi tertentu di pohon.

const K& GetKeyAt(POSITION pos) const throw();

Parameter

pos
Nilai posisi.

Tampilkan Nilai

Mengembalikan kunci yang disimpan pada posisi pos di pohon.

Keterangan

Jika pos bukan nilai posisi yang valid, hasilnya tidak dapat diprediksi. Dalam build debug, kegagalan pernyataan akan terjadi jika pos sama dengan NULL.

CRBTree::GetNext

Panggil metode ini untuk mendapatkan penunjuk ke elemen yang disimpan dalam CRBTree objek, dan lanjutkan posisi ke elemen berikutnya.

const CPair* GetNext(POSITION& pos) const throw();
CPair* GetNext(POSITION& pos) throw();

Parameter

pos
Penghitung posisi, dikembalikan oleh panggilan sebelumnya ke metode seperti CRBTree::GetHeadPosition atau CRBTree::FindFirstKeyAfter.

Tampilkan Nilai

Mengembalikan penunjuk ke nilai CPair berikutnya di pohon.

Keterangan

Penghitung posisi pos diperbarui setelah setiap panggilan. Jika elemen yang diambil adalah yang terakhir di pohon, pos diatur ke NULL.

CRBTree::GetNextAssoc

Panggil metode ini untuk mendapatkan kunci dan nilai elemen yang disimpan di peta dan lanjutkan posisi ke elemen berikutnya.

void GetNextAssoc(
    POSITION& pos,
    KOUTARGTYPE key,
    VOUTARGTYPE value) const;

Parameter

pos
Penghitung posisi, dikembalikan oleh panggilan sebelumnya ke metode seperti CRBTree::GetHeadPosition atau CRBTree::FindFirstKeyAfter.

kunci
Parameter templat yang menentukan jenis kunci pohon.

value
Parameter templat yang menentukan jenis nilai pohon.

Keterangan

Penghitung posisi pos diperbarui setelah setiap panggilan. Jika elemen yang diambil adalah yang terakhir di pohon, pos diatur ke NULL.

CRBTree::GetNextKey

Panggil metode ini untuk mendapatkan kunci elemen yang disimpan di pohon dan lanjutkan posisi ke elemen berikutnya.

const K& GetNextKey(POSITION& pos) const throw();

Parameter

pos
Penghitung posisi, dikembalikan oleh panggilan sebelumnya ke metode seperti CRBTree::GetHeadPosition atau CRBTree::FindFirstKeyAfter.

Tampilkan Nilai

Mengembalikan referensi ke kunci berikutnya di pohon.

Keterangan

Memperbarui penghitung posisi saat ini, pos. Jika tidak ada entri lagi di pohon, penghitung posisi diatur ke NULL.

CRBTree::GetNextValue

Panggil metode ini untuk mendapatkan nilai elemen yang disimpan di pohon dan lanjutkan posisi ke elemen berikutnya.

const V& GetNextValue(POSITION& pos) const throw();
V& GetNextValue(POSITION& pos) throw();

Parameter

pos
Penghitung posisi, dikembalikan oleh panggilan sebelumnya ke metode seperti CRBTree::GetHeadPosition atau CRBTree::FindFirstKeyAfter.

Tampilkan Nilai

Mengembalikan referensi ke nilai berikutnya di pohon.

Keterangan

Memperbarui penghitung posisi saat ini, pos. Jika tidak ada entri lagi di pohon, penghitung posisi diatur ke NULL.

CRBTree::GetPrev

Panggil metode ini untuk mendapatkan penunjuk ke elemen yang disimpan dalam CRBTree objek, lalu perbarui posisi ke elemen sebelumnya.

const CPair* GetPrev(POSITION& pos) const throw();
CPair* GetPrev(POSITION& pos) throw();

Parameter

pos
Penghitung posisi, dikembalikan oleh panggilan sebelumnya ke metode seperti CRBTree::GetHeadPosition atau CRBTree::FindFirstKeyAfter.

Tampilkan Nilai

Mengembalikan penunjuk ke nilai CPair sebelumnya yang disimpan di pohon.

Keterangan

Memperbarui penghitung posisi saat ini, pos. Jika tidak ada entri lagi di pohon, penghitung posisi diatur ke NULL.

CRBTree::GetTailPosition

Panggil metode ini untuk mendapatkan nilai posisi untuk elemen di ekor pohon.

POSITION GetTailPosition() const throw();

Tampilkan Nilai

Mengembalikan nilai posisi untuk elemen di ekor pohon.

Keterangan

Nilai yang dikembalikan oleh GetTailPosition dapat digunakan dengan metode seperti CRBTree::GetKeyAt atau CRBTree::GetPrev untuk melintasi pohon dan mengambil nilai.

CRBTree::GetValueAt

Panggil metode ini untuk mengambil nilai yang disimpan pada posisi tertentu dalam CRBTree objek.

const V& GetValueAt(POSITION pos) const throw();
V& GetValueAt(POSITION pos) throw();

Parameter

pos
Penghitung posisi, dikembalikan oleh panggilan sebelumnya ke metode seperti CRBTree::GetHeadPosition atau CRBTree::FindFirstKeyAfter.

Tampilkan Nilai

Mengembalikan referensi ke nilai yang disimpan pada posisi yang CRBTree diberikan dalam objek.

CRBTree::IsEmpty

Panggil metode ini untuk menguji objek pohon kosong.

bool IsEmpty() const throw();

Tampilkan Nilai

Mengembalikan TRUE jika pohon kosong, FALSE jika tidak.

CRBTree::KINARGTYPE

Jenis yang digunakan saat kunci diteruskan sebagai argumen input.

typedef KTraits::INARGTYPE KINARGTYPE;

CRBTree::KOUTARGTYPE

Jenis yang digunakan saat kunci dikembalikan sebagai argumen output.

typedef KTraits::OUTARGTYPE KOUTARGTYPE;

CRBTree::RemoveAll

Panggil metode ini untuk menghapus semua elemen dari CRBTree objek.

void RemoveAll() throw();

Keterangan

CRBTree Menghapus objek, membebaskan memori yang digunakan untuk menyimpan elemen.

CRBTree::RemoveAt

Panggil metode ini untuk menghapus elemen pada posisi yang diberikan dalam CRBTree objek.

void RemoveAt(POSITION pos) throw();

Parameter

pos
Penghitung posisi, dikembalikan oleh panggilan sebelumnya ke metode seperti CRBTree::GetHeadPosition atau CRBTree::FindFirstKeyAfter.

Keterangan

Menghapus pasangan kunci/nilai yang disimpan pada posisi yang ditentukan. Memori yang digunakan untuk menyimpan elemen dibebesarkan. POSISI yang direferensikan oleh pos menjadi tidak valid, dan sementara POSISI elemen lain di pohon tetap valid, mereka tidak selalu mempertahankan urutan yang sama.

CRBTree::SetValueAt

Panggil metode ini untuk mengubah nilai yang disimpan pada posisi tertentu dalam CRBTree objek.

void SetValueAt(POSITION pos, VINARGTYPE value);

Parameter

pos
Penghitung posisi, dikembalikan oleh panggilan sebelumnya ke metode seperti CRBTree::GetHeadPosition atau CRBTree::FindFirstKeyAfter.

value
Nilai yang akan ditambahkan ke CRBTree objek.

Keterangan

Mengubah elemen nilai yang disimpan pada posisi yang CRBTree diberikan dalam objek.

CRBTree::VINARGTYPE

Jenis yang digunakan saat nilai diteruskan sebagai argumen input.

typedef VTraits::INARGTYPE VINARGTYPE;

CRBTree::VOUTARGTYPE

Jenis yang digunakan saat nilai diteruskan sebagai argumen output.

typedef VTraits::OUTARGTYPE VOUTARGTYPE;

Lihat juga

Gambaran Umum Kelas