Struktur data dengan JavaScript: Tree

Indonesian (Bahasa Indonesia) translation by Dendi Deden (you can also view the original English article)

Final product image — What You'll Be Creating

Tree adalah salah satu struktur data yang paling umum digunakan dalam pengembangan web. Pernyataan ini berlaku untuk pengguna dan pengembang. Setiap web developer yang telah ditulis HTML dan dimuat ke web browser telah menciptakan sebuah tree, yang disebut sebagai Document Object Model (DOM). Setiap pengguna internet yang memiliki, pada gilirannya, mengkonsumsi informasi di Internet telah menerimanya dalam bentuk tree — DOM.

Sekarang, di sini adalah klimaks: artikel yang Anda baca saat ini dituliskan di peramban sebagai tree! paragprah yang baca direpresentasikan sebagai teks dalam<p>elemen; <p>elemen bersarang di dalam<body>elemen; dan<body>elemen bersarang di dalam<html>elemen.

data Bersarang ini mirip dengan sebuah pohon keluarga. <html>elemen adalah parent,<body>elemen adalah seorang child, dan<p>elemen adalah anak<body>elemen. Jika analogi ini pohon tampaknya berguna bagi Anda, maka Anda akan menemukan kenyamanan dalam mengetahui bahwa analogi lain akan digunakan selama kami pelaksanaan tree.

Dalam artikel ini, kita akan menciptakan sebuah pohon yang menggunakan dua metode yang berbeda dari pohon traversal: Depth-First Search (DFS) dan Breadth-First Search (BFS). (Jika kata traversal asing bagi Anda, mempertimbangkan hal itu berarti mengunjungi setiap node tree.) Kedua jenis traversals menyoroti berbagai cara berinteraksi dengan sebuah pohon. perjalanan kedua, Selain itu, menggabungkan penggunaan struktur data yang kita sudah dibahas dalam seri ini. DFS menggunakan tumpukan dan BFS menggunakan antrian untuk mengunjungi node. Ini keren!

Tree (Depth-First Search dan Breadth-First Search)

Dalam ilmu komputer, tree adalah struktur data yang mensimulasikan hirarkis data dengan node. Setiap node tree memegang sendiri data dan pointer ke node lain.

Terminologi node dan petunjuk mungkin baru bagi beberapa pembaca, jadi mari kita menggambarkan mereka lebih jauh dengan analogi. Mari kita bandingkan tree untuk bagan organisasi. Bagan memiliki posisi tingkat atas (root), seperti CEO. Tepat di bawah posisi ini adalah posisi lain, seperti Wakil Presiden (VP).

Untuk mewakili hubungan ini, kita menggunakan panah yang mengarah dari CEO kepada VP. Posisi, seperti CEO, adalah sebuah node; hubungan yang kita buat dari CEO kepada VP adalah pointer. Untuk membuat hubungan yang lebih dalam bagan organisasi kami, kami hanya mengulangi proses ini-kami memiliki sebuah node yang mengarah ke node lain.

Pada tingkat konseptual, saya berharap bahwa node dan pointer dipahami. Pada tingkat praktis, kita dapat manfaat dari menggunakan sebuah contoh yang lebih teknis. Mari kita mempertimbangkan DOM. DOM memiliki elemen<html>sebagai posisinya top-level (root). Node ini menunjuk kepada<head>elemen dan<body>elemen. Ini proses diulang untuk semua node di DOM.

Salah satu keindahan desain ini adalah kemampuan untuk sarang node: elemen <ul>yang, misalnya, dapat memiliki banyak<li element yang bersarang di dalamnya; Selain itu, setiap<li>elemen dapat memiliki saudara kandung<li>node. Itu aneh, tapi lucu dan benar!

Operasi Tree

Karena setiap tree berisi node, yang dapat constructor yang terpisah dari tree, kami akan menjelaskan operasi konstruktor kedua: Node dan Tree.

Node

data menyimpan nilai.
parent menunjuk ke sebuah node parent.
children poin ke node berikutnya dalam daftar.

Tree

_root poin untuk root node tree.
traverseDF(callback) melintasi node pohon dengan DFS.
traverseBF(callback) melintasi node pohon dengan BFS.
contains(data, traversal) mencari untuk sebuah node di tree.
add(data, toData, melintasi) menambahkan sebuah node di tree.
remove(child, parent) menghapus sebuah node dalam tree.

Implementasi Tree

Sekarang mari kita menulis kode untuk tree!

Properti dari Node

Untuk pelaksanaan, kita pertama akan mendefinisikan fungsi bernama Node dan kemudian constructor yang bernama Tree.

function Node(data) {
    this.data = data;
    this.parent = null;
    this.children = [];
}

Setiap contoh node berisi tiga properti: data, parent, dan children. Properti pertama memegang data yang terkait dengan sebuah node. Properti kedua menunjuk satu node. Properti ketiga menunjukkan banyak node children.

Properti Tree

Sekarang, mari kita menentukan konstruktor untuk Tree, yang meliputi konstruktor Node dalam definisi:

1	function Tree(data) {
2	var node = new Node(data);
3	this._root = node;
4	}

Tree berisi dua baris kode. Baris pertama menciptakan sebuah instance baru dari Node; baris kedua menetapkan node sebagai root dari tree.

Definisi dari Tree dan Node memerlukan hanya beberapa baris kode. Baris-baris ini, namun, yang cukup untuk membantu kami mensimulasikan hirarkis data. Untuk membuktikan hal ini, mari kita gunakan beberapa contoh data untuk membuat sebuah instance dari Tree (dan, secara tidak langsung, Node).

1	var tree = new Tree('CEO');
2
3	// {data: 'CEO', parent: null, children: []}
4	tree._root;

Berkat adanya parent dan children, kita dapat menambahkan node sebagai children _root dan juga menetapkan _root sebagai parent dari node tersebut. Dengan kata lain, kita dapat mensimulasikan penciptaan hirarkis data.

Metode Tree

Selanjutnya, kita akan menciptakan lima metode berikut:

Tree

traverseDF(callback)
traverseBF(callback)
contains(data, traversal)
add(Child, Parent)
remove(node, parent)

Karena setiap metode tree mengharuskan kita untuk melintasi pohon, kami pertama akan menerapkan metode yang menentukan jenis tree traversal. (Melintasi tree adalah cara formal mengatakan mengunjungi setiap node tree.)

1 dari 5: traverseDF(callback)

Metode ini melintasi tree dengan depth-first search

Tree.prototype.traverseDF = function(callback) {

    // this is a recurse and immediately-invoking function 
    (function recurse(currentNode) {
        // step 2
        for (var i = 0, length = currentNode.children.length; i < length; i++) {
            // step 3
            recurse(currentNode.children[i]);
        }

        // step 4
        callback(currentNode);
        
        // step 1
    })(this._root);

};

traverseDF(callback) memiliki parameter bernama callback. Jika tidak jelas dari nama, callback diduga menjadi fungsi, yang akan dipanggil kemudian di traverseDF(callback).

body traverseDF(callback) termasuk fungsi lain yang bernama recurse. Fungsi ini adalah fungsi rekursif! Dengan kata lain, self-invoking dan self-terminating. Menggunakan langkah-langkah yang disebutkan dalam komentar-komentar dari recurse, saya akan menjelaskan proses umum yang recurse menggunakan untuk melintasi seluruh tree.

Berikut adalah langkah-langkah:

Segera memanggil recurse dengan root node dari tree sebagai argumen. Saat ini, currentNode poin ke node saat ini.
Masukkan for loop dan iterate sekali untuk setiap child dari currentNode, dimulai dengan child pertama.
Di dalam body for loop, memanggil recurse dengan child dari currentNode. Anak yang tepat tergantung pada iterasi saat ini dari for loop.
Ketika currentNode tidak lagi memiliki children, kita keluar for loop dan invoke callback kami masukan selama invocation traverseDF(callback).

Langkah 2 (self-terminating), 3 (self-invoking), dan 4 (callback) ulangi sampai kita melintasi setiap node tree.

Rekursi adalah topik yang sangat sulit untuk mengajar dan memerlukan seluruh artikel untuk menjelaskan secara memadai. Karena penjelasan rekursi tidak fokus dari artikel ini — fokus mengimplementasikan tree-saya akan menyarankan bahwa setiap pembaca yang kurang memahami baik dari rekursi melakukan dua hal berikut.

Pertama, bereksperimen dengan pelaksanaan traverseDF(callback) kami saat ini dan mencoba untuk memahami tingkat cara kerjanya. Kedua, jika Anda ingin saya untuk menulis sebuah artikel tentang rekursi, kemudian silakan permintaan itu dalam komentar-komentar dari artikel ini.

Contoh berikut menunjukkan bagaimana tree yang akan dilalui dengan traverseDF(callback). Untuk melintasi tree, saya akan membuat satu dalam contoh di bawah ini. Pendekatan yang saya akan gunakan saat ini tidak ideal, tetapi bekerja. Pendekatan yang lebih baik akan menggunakan add(value), yang kami akan terapkan pada langkah 4 dari 5.

var tree = new Tree('one');

tree._root.children.push(new Node('two'));
tree._root.children[0].parent = tree;

tree._root.children.push(new Node('three'));
tree._root.children[1].parent = tree;

tree._root.children.push(new Node('four'));
tree._root.children[2].parent = tree;

tree._root.children[0].children.push(new Node('five'));
tree._root.children[0].children[0].parent = tree._root.children[0];

tree._root.children[0].children.push(new Node('six'));
tree._root.children[0].children[1].parent = tree._root.children[0];

tree._root.children[2].children.push(new Node('seven'));
tree._root.children[2].children[0].parent = tree._root.children[2];

/*

creates this tree

 one
 ├── two
 │   ├── five
 │   └── six
 ├── three
 └── four
     └── seven

*/

Sekarang, mari kita memanggil traverseDF(callback).

tree.traverseDF(function(node) {
    console.log(node.data)
});

/*

logs the following strings to the console

'five'
'six'
'two'
'three'
'seven'
'four'
'one'

*/

2 dari 5: traverseBF(callback)

Metode ini menggunakan breadth-first search untuk melintasi tree.

Perbedaan antara depth-first search dan pbreadth-first search melibatkan urutan yang mengunjungi node tree. Untuk mengilustrasikan hal ini, mari kita gunakan tree yang kita diciptakan dari traverseDF(callback).

/*

 tree

 one (depth: 0)
 ├── two (depth: 1)
 │   ├── five (depth: 2)
 │   └── six (depth: 2)
 ├── three (depth: 1)
 └── four (depth: 1)
     └── seven (depth: 2)

 */

Sekarang, mari kita masukan traverseBF(callback) callback sama yang kita gunakan untuk traverseDF(callback).

tree.traverseBF(function(node) {
    console.log(node.data)
});

/*

logs the following strings to the console

'one'
'two'
'three'
'four'
'five'
'six'
'seven'

*/

Log dari konsol dan diagram tree kami mengungkapkan pola tentang breadth-first search. Mulai dengan root node; Kemudian perjalanan satu kedalaman dan mengunjungi setiap node dalam bahwa kedalaman dari kiri ke kanan. Ulangi proses ini sampai ada kedalaman tidak lebih untuk melakukan perjalanan.

Karena kita memiliki model konseptual breadth-first search mari kita sekarang menerapkan kode yang akan membuat contoh kita bekerja.

Tree.prototype.traverseBF = function(callback) {
    var queue = new Queue();
    
    queue.enqueue(this._root);

    currentTree = queue.dequeue();

    while(currentTree){
        for (var i = 0, length = currentTree.children.length; i < length; i++) {
            queue.enqueue(currentTree.children[i]);
        }

        callback(currentTree);
        currentTree = queue.dequeue();
    }
};

Definisi kita tentang traverseBF(callback) berisi banyak logika. Untuk alasan ini, saya akan menjelaskan logika dalam langkah-langkah yang dikelola:

Membuat sebuah instance dari Queue.
Menambahkan node yang dipanggil traverseBF(callback) untuk instance Queue.
Mendeklarasikan variabel bernama currentNode dan menginisialisasi ke node kami hanya menambahkan ke queue kami.
Sementara currentNode poin untuk sebuah node, mengeksekusi kode dalam while loop.
menggunakan for loop untuk interasi pada children dari currentNode.
Di dalam body for loop, menambahkan setiap anak untuk queue.
Ambil currentNode dan masukan sebagai argumen callback.
Menetapkan kembali currentNode ke node yang dihapus dari queue.
Sampai currentNode tidak menunjuk ke sebuah node — setiap node dalam tree telah dikunjungi — ulangi langkah 4-8.

3 dari 5: contains(callback, traversal)

Mari kita mendefinisikan sebuah metode yang akan memungkinkan kita untuk mencari untuk nilai yang tertentu di tree kita. Untuk menggunakan salah satu metode kami dari tree traversal, aku sudah didefinisikan contains(callback, traversal) untuk menerima dua argumen: data pencarian dan jenis traversal.

1	Tree.prototype.contains = function(callback, traversal) {
2	traversal.call(this, callback);
3	};

Dalam body contains(callback, traversal), kami menggunakan metode bernama call untuk memasukan this dan callback. Berisi argumen pertama mengikat traversal menuju tree yang menanggil contains(callback, traversal); argumen kedua adalah fungsi yang dipanggil pada setiap node dalam tree kami.

Bayangkan bahwa kita ingin login ke konsol setiap node yang berisi data dengan angka ganjil dan melintasi setiap node dalam tree kami dengan BFS. Ini adalah kode yang kita akan tulis:

// tree is an example of a root node
tree.contains(function(node){
    if (node.data === 'two') {
        console.log(node);
    }
}, tree.traverseBF);

4 dari 5: add(data, toData, traversal)

Kami sekarang memiliki sebuah metode untuk mencari sebuah node tertentu di tree kita. Mari kita sekarang mendefinisikan sebuah metode yang akan memungkinkan kita untuk menambahkan sebuah node ke node tertentu.

Tree.prototype.add = function(data, toData, traversal) {
    var child = new Node(data),
        parent = null,
        callback = function(node) {
            if (node.data === toData) {
                parent = node;
            }
        };

    this.contains(callback, traversal);

    if (parent) {
        parent.children.push(child);
        child.parent = parent;
    } else {
        throw new Error('Cannot add node to a non-existent parent.');
    }
};

add(data, toData, traversal) mendefinisikan tiga parameter. Parameter pertama, data, digunakan untuk membuat sebuah instance baru dari Node. Parameter kedua, toData, digunakan untuk membandingkan terhadap setiap node dalam sebuah tree. Parameter ketiga, traversal, jenis tree traversal digunakan dalam metode ini.

Dalam body add(data, toData, traversal), kita menyatakan ketiga variabel. Variabel pertama, child, diinisialisasi sebagai sebuah instance baru dari Node. Kedua variabel, parent, diinisialisasi sebagai null; tetapi ia kemudian akan menunjuk ke setiap node di tree yang cocok dengan nilai toData. reassignment dari parent yang terjadi dalam variabel ketiga kami menyatakan, yang adalah callback.

callback adalah fungsi yang membandingkan toData untuk setiap node data properti. Jika if pernyataan mengevaluasi true, maka parent diberikan ke node yang cocok dengan if pernyataan.

Perbandingan aktual setiap node untuk toData terjadi di contains(callback, traversal). Jenis traversal dan callback harus dimasukan sebagai argumen dari contains(callback, traversal).

Akhirnya, jika parent ada di pohon, kami mendorong child ke parent.children; Kami juga menetapkan parent untuk parent dari child. Else, kita melempar error

Mari kita gunakan add(data, toData, traversal) dalam sebuah contoh:

var tree = new Tree('CEO');

tree.add('VP of Happiness', 'CEO', tree.traverseBF);

/*

our tree

'CEO'
└── 'VP of Happiness'

*/

Berikut adalah contoh yang lebih kompleks add(addData, toData, traversal):

var tree = new Tree('CEO');

tree.add('VP of Happiness', 'CEO', tree.traverseBF);
tree.add('VP of Finance', 'CEO', tree.traverseBF);
tree.add('VP of Sadness', 'CEO', tree.traverseBF);

tree.add('Director of Puppies', 'VP of Finance', tree.traverseBF);
tree.add('Manager of Puppies', 'Director of Puppies', tree.traverseBF);

/*

 tree

 'CEO'
 ├── 'VP of Happiness'
 ├── 'VP of Finance'
 │   ├── 'Director of Puppies'
 │   └── 'Manager of Puppies'
 └── 'VP of Sadness'

 */

5 dari 5: remove(data, fromData, traversal)

Untuk menyelesaikan implementasi Tree, kita akan menambahkan sebuah metode bernama remove(data, fromData, traversal). Mirip dengan menghapus sebuah node dari DOM, metode ini akan menghapus sebuah node dan semua children.

Tree.prototype.remove = function(data, fromData, traversal) {
    var tree = this,
        parent = null,
        childToRemove = null,
        index;

    var callback = function(node) {
        if (node.data === fromData) {
            parent = node;
        }
    };

    this.contains(callback, traversal);

    if (parent) {
        index = findIndex(parent.children, data);

        if (index === undefined) {
            throw new Error('Node to remove does not exist.');
        } else {
            childToRemove = parent.children.splice(index, 1);
        }
    } else {
        throw new Error('Parent does not exist.');
    }

    return childToRemove;
};

Serupa dengan add(data, toData, traversal), Hapus melintasi tree untuk menemukan sebuah node yang berisi argumen kedua, yang sekarang fromData. Jika node ini ditemukan, maka parent poin ke itu.

Saat ini, kita mencapai if pernyataan pertama. Jika parent tidak ada, kita melempar error. Jika parent ada, kita memanggil findIndex() dengan parent.children dan data yang ingin kita Hapus dari node child dari orangtua. (findIndex() adalah metode helper yang aku didefinisikan di bawah ini.)

function findIndex(arr, data) {
    var index;

    for (var i = 0; i < arr.length; i++) {
        if (arr[i].data === data) {
            index = i;
        }
    }

    return index;
}

Di dalam findIndex(), logika berikut terjadi. Jika salah satu node dalam parent.children berisi data yang sesuai data, index variabel ditetapkan sebagai integer. Jika tak satu pun dari children data properti sesuai data, kemudian index mempertahankan nilai default dari undefined. Pada baris terakhir dari findIndex(), kita mengembalikan index.

Sekarang kita kembali ke remove(data, fromData, traversal). Jika index adalah undefined, error dilemparkan. Jika index didefinisikan, kita menggunakannya untuk menyambung node yang ingin kita Hapus dari children dari parent; Kami juga menetapkan child dihapus untuk childToRemove.

Akhirnya, kita kembalikan childToRemove.

Implementasi lengkap Tree

Implementasi lengkap Tree. Lihat — kami telah mencapai banyak:

function Node(data) {
    this.data = data;
    this.parent = null;
    this.children = [];
}

function Tree(data) {
    var node = new Node(data);
    this._root = node;
}

Tree.prototype.traverseDF = function(callback) {

    // this is a recurse and immediately-invoking function
    (function recurse(currentNode) {
        // step 2
        for (var i = 0, length = currentNode.children.length; i < length; i++) {
            // step 3
            recurse(currentNode.children[i]);
        }

        // step 4
        callback(currentNode);

        // step 1
    })(this._root);

};

Tree.prototype.traverseBF = function(callback) {
    var queue = new Queue();

    queue.enqueue(this._root);

    currentTree = queue.dequeue();

    while(currentTree){
        for (var i = 0, length = currentTree.children.length; i < length; i++) {
            queue.enqueue(currentTree.children[i]);
        }

        callback(currentTree);
        currentTree = queue.dequeue();
    }
};

Tree.prototype.contains = function(callback, traversal) {
    traversal.call(this, callback);
};

Tree.prototype.add = function(data, toData, traversal) {
    var child = new Node(data),
        parent = null,
        callback = function(node) {
            if (node.data === toData) {
                parent = node;
            }
        };

    this.contains(callback, traversal);

    if (parent) {
        parent.children.push(child);
        child.parent = parent;
    } else {
        throw new Error('Cannot add node to a non-existent parent.');
    }
};

Tree.prototype.remove = function(data, fromData, traversal) {
    var tree = this,
        parent = null,
        childToRemove = null,
        index;

    var callback = function(node) {
        if (node.data === fromData) {
            parent = node;
        }
    };

    this.contains(callback, traversal);

    if (parent) {
        index = findIndex(parent.children, data);

        if (index === undefined) {
            throw new Error('Node to remove does not exist.');
        } else {
            childToRemove = parent.children.splice(index, 1);
        }
    } else {
        throw new Error('Parent does not exist.');
    }

    return childToRemove;
};

function findIndex(arr, data) {
    var index;

    for (var i = 0; i < arr.length; i++) {
        if (arr[i].data === data) {
            index = i;
        }
    }

    return index;
}

Kesimpulan

Tree mensimulasikan hirarkis data. Sebagian besar dunia di sekitar kita menyerupai jenis hirarki, seperti halaman web dan keluarga kita. Setiap kali Anda menemukan diri Anda membutuhkan struktur data dengan hirarki, pertimbangkan untuk menggunakan sebuah Tree.

1	var tree = new Tree('one');
2
3	tree._root.children.push(new Node('two'));
4	tree._root.children[0].parent = tree;
5
6	tree._root.children.push(new Node('three'));
7	tree._root.children[1].parent = tree;
8
9	tree._root.children.push(new Node('four'));
10	tree._root.children[2].parent = tree;
11
12	tree._root.children[0].children.push(new Node('five'));
13	tree._root.children[0].children[0].parent = tree._root.children[0];
14
15	tree._root.children[0].children.push(new Node('six'));
16	tree._root.children[0].children[1].parent = tree._root.children[0];
17
18	tree._root.children[2].children.push(new Node('seven'));
19	tree._root.children[2].children[0].parent = tree._root.children[2];
20
21	/*
22
23	creates this tree
24
25	one
26	├── two
27	│ ├── five
28	│ └── six
29	├── three
30	└── four
31	└── seven
32
33	*/

1	function Node(data) {
2	this.data = data;
3	this.parent = null;
4	this.children = [];
5	}
6
7	function Tree(data) {
8	var node = new Node(data);
9	this._root = node;
10	}
11
12	Tree.prototype.traverseDF = function(callback) {
13
14	// this is a recurse and immediately-invoking function
15	(function recurse(currentNode) {
16	// step 2
17	for (var i = 0, length = currentNode.children.length; i < length; i++) {
18	// step 3
19	recurse(currentNode.children[i]);
20	}
21
22	// step 4
23	callback(currentNode);
24
25	// step 1
26	})(this._root);
27
28	};
29
30	Tree.prototype.traverseBF = function(callback) {
31	var queue = new Queue();
32
33	queue.enqueue(this._root);
34
35	currentTree = queue.dequeue();
36
37	while(currentTree){
38	for (var i = 0, length = currentTree.children.length; i < length; i++) {
39	queue.enqueue(currentTree.children[i]);
40	}
41
42	callback(currentTree);
43	currentTree = queue.dequeue();
44	}
45	};
46
47	Tree.prototype.contains = function(callback, traversal) {
48	traversal.call(this, callback);
49	};
50
51	Tree.prototype.add = function(data, toData, traversal) {
52	var child = new Node(data),
53	parent = null,
54	callback = function(node) {
55	if (node.data === toData) {
56	parent = node;
57	}
58	};
59
60	this.contains(callback, traversal);
61
62	if (parent) {
63	parent.children.push(child);
64	child.parent = parent;
65	} else {
66	throw new Error('Cannot add node to a non-existent parent.');
67	}
68	};
69
70	Tree.prototype.remove = function(data, fromData, traversal) {
71	var tree = this,
72	parent = null,
73	childToRemove = null,
74	index;
75
76	var callback = function(node) {
77	if (node.data === fromData) {
78	parent = node;
79	}
80	};
81
82	this.contains(callback, traversal);
83
84	if (parent) {
85	index = findIndex(parent.children, data);
86
87	if (index === undefined) {
88	throw new Error('Node to remove does not exist.');
89	} else {
90	childToRemove = parent.children.splice(index, 1);
91	}
92	} else {
93	throw new Error('Parent does not exist.');
94	}
95
96	return childToRemove;
97	};
98
99	function findIndex(arr, data) {
100	var index;
101
102	for (var i = 0; i < arr.length; i++) {
103	if (arr[i].data === data) {
104	index = i;
105	}
106	}
107
108	return index;
109	}