RSS
email
0

2-3-4 Tree


2-3-4 Tree
Sebuah pohon 2-3-4 (juga disebut pohon 2-4), dalam ilmu komputer, disebutkan sebagai struktur data  menyeimbangkan diri  yang umumnya digunakan untuk mengimplementasikan kamus.  2-3-4 pohon adalah pohon B-order  4; seperti B-pohon pada umumnya, mereka dapat mencari, menyisipkan dan menghapus dalam O  (log n) waktu. Satu properti sebuah pohon 2-3-4 adalah bahwa semua node eksternal berada pada kedalaman yang sama.

2-3-4 pohon adalah isometry  dari pohon hitam merah,  yang berarti bahwa mereka struktur data  setara. Dengan kata lain, untuk setiap 2-3-4 pohon, terdapat paling tidak satu pohon merah-hitam dengan elemen data dalam urutan yang sama. Selain itu, penyisipan dan penghapusan 2-3-4 operasinya pada pohon-pohon yang menyebabkan ekspansi simpul, perpecahan dan gabungan yang setara dengan warna-membalik dan rotasi pohon merah-hitam. Perkenalan ke merah-hitam biasanya pohon pohon 2-3-4 memperkenalkan pertama, karena mereka secara konseptual sederhana. Pohon 2-3-4 Namun, mungkin sulit untuk mengimplementasikan di kebanyakan bahasa pemrograman karena jumlah besar kasus khusus yang terlibat dalam operasi di pohon. Merah-pohon hitam  yang mudah untuk diterapkan, jadi cenderung untuk digunakan sebagai gantinya.

Insert
Untuk memasukkan nilai, kita mulai dari akar pohon 2-3-4:
  1. Jika node saat ini adalah 4-node:
  • Mendorong elemen tengah dari 4-node menjadi orangtua, meninggalkan 3-node.
  • Split sisanya 3-simpul menjadi sepasang 2-node.
  • Jika ini adalah akar simpul (yang dengan demikian tidak memiliki orang tua), nilai tengah menjadi akar baru 2-node dan tinggi pohon meningkat sebesar 1. Naik ke akar.
  • Jika tidak, mendorong nilai tengah menjadi simpul orangtua. Naik ke simpul orangtua.
  1. Menemukan anak yang mengandung nilai interval untuk dimasukkan.
  2. Jika anak tersebut kosong, masukkan nilai ke dalam simpul saat ini dan selesai.
Jika tidak, turun ke anak dan ulangi dari langkah



Delete (Penghapusan)

Penghapusan adalah operasi yang lebih kompleks dan melibatkan banyak kasus khusus. Pertama elemen yang akan dihapus harus ditemukan. Elemen harus dalam sebuah simpul di bagian bawah pohon; sebaliknya, hal itu harus bertukar dengan elemen lain yang mendahului dalam in-order traversal (yang harus ada di node paling bawah) dan bahwa elemen dihapus saja.

Jika elemen yang akan dihapus dari suatu 2-node, maka sebuah simpul yang tidak memiliki unsur-unsur akan menghasilkan. Ini disebut underflow. Untuk memecahkan underflow, sebuah elemen ditarik dari orangtua simpul ke simpul di mana elemen dihapus dan kekosongan diciptakan dalam simpul ayah diganti dengan elemen dari simpul saudara. (Saudara node adalah mereka yang berbagi orang tua yang sama node.) Hal ini disebut transfer.

Jika saudara adalah 2-node sendiri, underflow masih terjadi, karena sekarang saudara tidak mempunyai elemen. Untuk mengatasi ini, dua saudara kandung node yang digabungkan bersama (setelah menarik elemen dari simpul orangtua).

Jika orangtua adalah 2-node, underflow akan terjadi pada node induk. Hal ini diselesaikan dengan menggunakan metode di atas. Ini dapat menyebabkan node orangtua yang berbeda untuk mempertahankan underflow sebagai pengganti penghapusan dan sedang dilakukan, yang disebut sebagai cascading underflow.

Penghapusan dalam pohon 2-3-4 adalah O (log n), sementara transfer dan fusi waktu konstan,
Read more
0

Red Black Tree

RED BLACK TREE
Red-Balck Tree (RBT) adalah sebuah BST (binary search tree) dimana tiap simpul memiliki atribut warna yang bernilai merah atau hitam.
            RBT juga berguna dalam pemrograman fungsional karena RBT merupakan salah satu struktur data yang paling “persistent”, digunakan untuk membuat associative array dan himpunan yang bhisa mengambil kembali versi sebelumnya setelah perubahan. Versi “persistent” dari RBT memerlukan tambahan ruang O(log n) untuk setiap insersi atau delesi, selain waktu.
RBT isometri dari pohon 2-3-4. Artinya, untuk setiap 2-3-4 pohon, terdapat paling sedikit satu satu RBT dengan elemen data yang berurutan sama. Operasi insersi dan delesi pada pohon 2-3-4 equivalen dengan color-flipping (pertukaran warna) dan rotasi pada RBT. Ini membuat pohon 2-3-4 alat yang penting untuk memahami logika dibalik RBT, hal ini pula yang membuat berbagai text algoritma memperkenalkan pohon 2-3-4 sebelum RBT walaupun pohon 2-3-4 lebih jarang digunakan.
Red Black Tree adalah suatu BST( Binary Search Tree) dimana node-node dan edge-edge memiliki warna merah atau hitam. Warna dari root selalu hitam. Warna dari edge yang menghubungkan ayah dengan anaknya selalu berwarna sama dengan warna node anak tersebut. Selain atribut yang dimiliki oleh BST, kita memerlukan persyaratan berikut untuk memnentukan
validitas RBT :

Aturan pada Red Black Tree :
1.      Setiap simpul/node adalah berwarna merah atau hitam
2.      Akar selalu berwarna hitam
3.      Nilai sebuah node adalah lebih besar anak kirinya dan lebih kecil dari anak kanannya.
4.      Jika node berwarna merah, anaknya harus berwarna hitam
5.      Node berwarna merah secara berturut-turut tidak diperkenankan.
6.      Setiap path dari node yang menuju ke nil harus mengandung nilai yang sama dengan node yang berwarna hitam.
7.      Tree dikatakan setimbang jika selisih level dari anak kiri dan anak kanan maksimal dua.
8.      Node dibawah root yang berada pada level yang sama disebut sibling.

Aturan Insert pada Red Black Tree :
1.      Setiap node baru yang disisipkan  kedalam tree akan diberi warna merah.
2.      Jika kita memberi warna hitam  pada node baru yang  masuk, maka jumlah node dari root akan berbeda.
3.      Jika kita memasukkan node baru yang berwarna merah kedalam parent yang berwarna hitam tidak akan menjadi masalah, yang menjadi masalah adalah jika kita menyisipkan node baru ke dalam parent yang berwarna merah
4.      Jika parent berwarna merah kita akan membuat dua node merah yang berurutan, jadi kita harus melakukan rotasi atau pewarnaan ulang.
5.      Hal penting yang harus diingat adalah node yang tidak mempunyai daun harus berwarna hitam.


 
Insertion
Penyisipan dimulai dengan menambahkan node seperti penyisipan pohon pencarian biner  dilakukan dan dengan mewarnai merah. Sedangkan dalam pohon pencarian biner, kita selalu menambahkan daun, merah-hitam daun pohon tidak mengandung informasi, jadi kita tambahkan node interior merah, dengan dua daun hitam, di tempat yang ada daun hitam.
Apa yang terjadi berikutnya tergantung pada warna terdekat lain node. Paman (saudara parent) dalam istilah node akan digunakan untuk merujuk pada saudara kandung dari node orangtua, seperti dalam pohon keluarga manusia. Perhatikan bahwa:
Properti 3 (Semua daun yang hitam) selalu berlaku.
Properti 4 (Baik anak-anak dari setiap node merah hitam) terancam hanya dengan menambahkan simpul merah, mengecat node hitam merah, atau rotasi.
Properti 5 (Semua path dari setiap node ke node daun berisi jumlah yang sama node hitam) terancam hanya dengan menambahkan node hitam, mengecat simpul merah hitam, atau rotasi.

Catatan: Label N akan digunakan untuk menunjukkan simpul sedang dimasukkan (berwarna merah); P akan menunjukkan N 's simpul ayah, G akan menyatakan N' s kakek-nenek, dan U akan menunjukkan N 's paman. Perhatikan bahwa di antara beberapa kasus, peran dan label simpul komunikasi, tetapi dalam setiap kasus, setiap label terus untuk mewakili simpul yang sama ini diwakili pada awal kasus. Setiap warna ditampilkan dalam diagram diasumsikan baik dalam kasus maupun tersirat oleh asumsi-asumsi ini.

Deleting (Penghapusan)
Dalam sebuah pohon pencarian biner yang normal, saat menghapus sebuah node dengan dua anak-anak non-daun, kita menemukan salah satu elemen maksimum dalam subtree kiri atau elemen minimum dalam subtree kanan, dan memindahkan nilainya ke dalam node yang dihapus . Kami kemudian menghapus simpul kita menyalin nilai dari, yang pasti kurang dari dua non-daun anak-anak. Karena hanya menyalin nilai tidak melanggar sifat merah-hitam, ini untuk mengurangi masalah menghapus sebuah node dengan paling banyak satu anak non-daun. Tidak peduli apakah simpul ini adalah simpul kami awalnya ingin menghapus atau simpul kita menyalin nilai dari.
Untuk masalah ini kita dapat mengasumsikan kita menghapus sebuah node dengan paling banyak satu daun non-anak, yang akan kita sebut dengan anak (jika ia hanya mempunyai anak-anak daun, membiarkan salah satu dari mereka menjadi para anak). Jika kita menghapus simpul merah, kita dapat dengan mudah menggantinya dengan anak, yang harus hitam. Semua jalan melalui node dihapus hanya akan melewati kurang satu simpul merah, dan kedua dihapus node orangtua dan anak harus hitam, jadi sifat 3 (Semua daun, termasuk null s, yang hitam) dan 4 (Kedua anak-anak dari setiap node merah hitam) masih terus. Lain kasus sederhana adalah ketika dihapus node anak hitam dan merah. Cukup menghapus simpul hitam bisa memecahkan Properti 4 (Baik anak-anak dari setiap node merah hitam) dan 5 (Semua path dari setiap node ke node daun berisi jumlah yang sama node hitam), tetapi jika kita mengecat kembali dengan anak hitam, baik properti ini dipertahankan.

Kasus yang rumit adalah ketika kedua simpul untuk dihapus dan anak yang hitam. Kita mulai dengan mengganti node untuk dihapus dengan anak. Kami akan panggilan (atau label) anak ini (dalam posisi baru) N, dan saudara (orangtua baru anak lain) S. Dalam diagram di bawah ini, kita juga akan menggunakan P untuk N 's orangtua baru, S L untuk S' s anak kiri, dan S R untuk S 's anak kanan (dapat ditunjukkan bahwa S tidak bisa menjadi daun).
Catatan: Di antara beberapa kasus, saling bertukar peran dan label dari node, tapi dalam setiap kasus, setiap label terus untuk mewakili simpul yang sama ini diwakili pada awal kasus. Setiap warna ditampilkan dalam diagram diasumsikan baik dalam kasus maupun tersirat oleh asumsi-asumsi ini. Putih merupakan warna yang tidak diketahui (baik merah atau hitam).



Read more
0

Tax Treaty
Suatu tax treaty pada dasarnya mencakup subjek pajak dua negara yang melaksanakannya. Dalam situasi tertentu, diperlukan kepastian bahwa suatu jenis penghasilan memang milik subjek pajak dari salah satu negara yang bersangkutan, yang lazim disebut dengan beneficial owner.
Penegasan agar penghasilan tersebut dapat dikenai pajak di negara sumber sesuai dengan ketentuan dalam tax treaty, mencakup dua hal, yaitu yang menerima penghasilan dimaksud adalah subjek pajak dari negara domisili, dan yang bersangkutan memang benar-benar yang memiliki penghasilan tersebut.
Penerapan dari beneficial owner ini dilakukan terhadap pembayaran bunga, royalti dan dividen. Apabila penghasilan tersebut dibayar kepada wajib pajak yang berdomisili di negara yang mempunyai tax treaty, maka pengenaan pajak di negara sumber tidak sepenuhnya sesuai dengan ketentuan undang-undang domestik, tetapi dibatasi oleh ketentuan sebagaimana diatur di dalam treaty yang bersangkutan.
Namun demikian, tidak berarti bahwa apabila penghasilan tersebut diterima oleh subjek pajak negara treaty partner lalu dengan sendirinya pengenaan pajaknya di negara sumber mengikuti treaty.
Dalam kaitannya dengan rumusan di dalam Treaty Model yang berbunyi "paid to a resident....." masih perlu ditambah dengan syarat bahwa subjek pajak tersebut adalah beneficial owner dari penghasilan dimaksud.
Dalam penjelasan Artikel 11, OECD Model menyebutkan bahwa conduit companies tidak dapat dianggap sebagai beneficial owner. Selanjutnya Commentary dari OECD menjelaskan istilah beneficial owner tidak boleh diartikan secara sempit, tetapi harus diartikan dalam konteks tujuan dari tax treaty yaitu mencegah terjadinya pengenaan pajak berganda. Commentary tersebut masih belum memberikan gambaran jelas dari istilah tersebut.
International Tax Glossary, (IBFD Publication BV) memberi definisi beneficial owner adalah orang yang memang berhak menikmati suatu aktiva. Jadi apabila seseorang atau badan secara hukum pemilik suatu aktiva, belum tentu yang bersangkutan adalah beneficial owner dari aktiva tersebut.
Vogel, dalam bukunya On Double Taxation Conventions, 1977, halaman 561-562, mengatakan treaty benefits seharusnya tidak diberikan kepada orang atau badan yang secara formal berhak atas dividen, royalty dan bunga, melainkan kepada orang atau badan yang menjadi pemegang "real" title. Dalam hal ini maka harus diterapkan prinsip "substance over form". Masalah "substance" atas hak untuk menerima suatu penghasilan mengandung dua aspek, yaitu: hak untuk menentukan apakah hasil tersebut direalisasikan atau tidak, yang dalam hal ini menyangkut apakah kekayaan atau aktiva dimaksud akan digunakan atau disediakan untuk digunakan, hak untuk menggunakan hasil dimaksud.
Jadi dapat dikatakan "beneficial owner", menurut Vogel, adalah, mereka yang bebas untuk menentukan: apakah kekayaan atau aktiva lainnya harus digunakan atau disediakan untuk digunakan oleh orang lain; atau bagaimana hasil dari kekayaan tersebut akan digunakan; atau ke dua hal yang disebutkan di muka.
Uraian di atas menunjukkan bahwa Vogel melihat masalah "control" merupakan faktor utama untuk menentukan "beneficial owner".
Charl P.du Toit, dalam bukunya yang berjudul Beneficial Ownership of Royalties in Bilateral Tax Treaties, halaman 91, mengatakan pendekatan yang diberikan Vogel tidak selalu dapat diterapkan karena kesulitan akan timbul jika pihak yang melakukan"control" berbeda dengan pihak yang menikmati. Contoh yang paling tepat untuk ini adalah apa yang disebut "trust".
Istilah "trust" adalah suatu legal arrangement antara pemilik properti (atau aktiva lain) - biasa disebut the settlor, yang memindahkan miliknya tersebut kepada - the trustee - yang wajib memegang dan menguasainya sesuai dengan instruksi dari the trustee, yang hasilnya akan dinikmati oleh orang-orang yang ditunjuk (the beneficiaries).
Misalkan suatu trustee ditunjuk mengelola aktiva, yang terdiri antara lain berupa intellectual property. Dalam pengelolaannya trustee tersebut memberikan hak mempergunakan intellectual property dimaksud kepada perusahaan di negara lain dan untuk itu pemakai hak tersebut membayar royalti.
Misalkan negara trustee berada dan negara pemakai hak berdomisili berlaku tax treaty maka persoalannya adalah apakah pengenaan pajak atas royalty yang dibayarkan kepada trustee tersebut memenuhi syarat untuk diterapkan tarif yang diatur di dalam treaty dimaksud.
Dalam situasi demikian, siapa yang dianggap sebagai beneficial owner dari royalti dimaksud. Apabila diterapkan tes yang diusulkan oleh Vogel, dalam situasi tersebut pihak yang dalam posisi untuk menentukan bagaimana suatu aktiva akan digunakan dengan pihak yang menentukan bagaimana hasil dari aktiva tersebut untuk digunakan, adalah berbeda.
Apabila diterapkan prinsip faktor terpenting adalah siapa yang mempunyai kekuatan "control" maka dalam contoh tersebut, trustee yang bersangkutan juga mempunyai "control". Bedanya adalah "control" dimaksud untuk kepentingan pihak lain, yaitu beneficiary.

DAFTAR PUSTAKA


Read more
 

Friends

ON-LINE