Bài viết trước mình đã giới thiệu cơ bản về đánh giá thuật toán với Big-O, cài đặt cấu trúc dữ liệu Linked list, bài viết này mình sẽ tiếp tục với cấu trúc dữ liệu dạng cây (tree).
Nội dung:
+ Giới thiệu về cấu trúc dữ liệu dạng cây
+ Phân loại
+ Cài đặt và thao tác
Giới thiệu cấu trúc cây
Nhìn chung một cấu trúc dữ liệu dạng cây được kết hợp từ nhiều nodes với nhiều nodes con. Node đầu tiên/ trên cùng được gọi là node gốc (root node) trong bài viết này chúng ta sẽ khám phá nhiều kiểu về cây khác nhau như là cây nhị phân, cây tìm kiếm nhị phân, cây tìm kiếm nhị phân tự cân bằng (self-balancing binary)…cây sẽ có dạng cơ bản:
Khối mã để triển khai một node tree như sau:function TreeNode(value) {Cây nhị phân (binary tree):
this.value = value;
this.children = [];
}
cây nhị phân là kiểu cây mà chỉ có hai node con trái và phải.
Cài đặt node cây nhị phân:function BinaryTreeNode (value){
this.value = value;
this.left = null;
this.right = null;
}
Một cây nhị phân luôn luôn có một node gốc, được khỏi tạo là null trước khi bất kì phần tử nào được chèn vào cây.function BinaryTree () {
this._root = null;
}
Duyệt cây:
Duyệt qua một mảng là đơn giản: truy cập node cây sử dụng chỉ số và tăng chỉ số cho đến khi chỉ số chạm tới kích thước giới hạn. Với cây,con trỏ trái và con trỏ phải , phải tuân theo thứ tự của mỗi phần tử trong cây. Có nhiều cách để làm việc này, các kĩ thuật duyệt phổ biến nhất là duyệt theo thứ tự trước, duyệt theo thứ tự sau, duyệt bên trong và duyệt theo thứ tự cấp độ của node (duyệt những node ngang hàng nhau trước.)
Duyệt theo thứ tự trước hay duyệt hàng trước ( Pre-order Traversal ):
Duyệt hàng trước duyệt qua các node theo thứ tự sau: root (node hiện tại), trái, phải. Trong hình bên dưới bạn nhìn thấy rằng 42 là root node nên nó được duyệt trước, khi đó tiếp tục qua bên trái, khi đó node trái (41) của node gốc được cân nhắc là root node, root node mới (41) được in, khi đó tiếp tục duyệt node bên trái của node này là 10, nên 10 sẽ được set là node gốc mới, nhưng sẽ không thể tiếp tục vì không có node con, khi đó 40 được duyệt bởi vì là node bên phải của node 41, việc xử lý như vậy tiếp tục và toàn bộ thứ tự các node trong cây được duyệt:
với đệ quy việc cài đặt là dễ dàng, trường hợp base để chấm dứt đệ quy khi node là null. Ngược lại nó sẽ in ra giá trị node và khi đó gọi hàm đệ quy bên con trái và khi đó con phải của nó:BinaryTree.prototype.traversePreOrder = function() {
traversePreOrderHelper(this._root);
function traversePreOrderHelper(node) {
if (!node) return;
console.log(node.value);
traversePreOrderHelper(node.left);
traversePreOrderHelper(node.right);
}
}
Điều này cũng có thể được hoàn thành với việc duyệt, nhưng khó hơn để cài đặt:BinaryTree.prototype.traversePreOrderIterative = function() {
//create an empty stack and push root to it
var nodeStack = [];
nodeStack.push(this._root);
// Pop all items one by one. Do following for every popped item
// a) print it
// b) push its right child
// c) push its left child
// Note that right child is pushed first so that left is processed first
while (nodeStack.length) {
//# Pop the top item from stack and print it
var node = nodeStack.pop();
console.log(node.value);
//# Push right and left children of the popped node to stack
if (node.right) nodeStack.push(node.right);
if (node.left) nodeStack.push(node.left);
}
}
đây là kết quả:: [42, 41, 10, 40, 50, 45, 75]Duyệt theo thứ tự trong ( In-Order Traversal ):
Duyệt các node theo thứ tự sau: trái, gốc (current node), phải.
Thứ thự duyệt:
Duyệt trong cũng được cài đặt dễ dàng với đệ quy. Trường hợp chấm dứt đệ quy là khi node là null. Trong trường hợp không phải cơ bản, gọi hàm đệ quy bên con trái, in node gốc, và khi đó gọi đệ quy bên con phải.BinaryTree.prototype.traverseInOrder = function() {
traverseInOrderHelper(this._root);
function traverseInOrderHelper(node) {
if (!node) return;
traverseInOrderHelper(node.left);
console.log(node.value);
traverseInOrderHelper (node.right);
}
}
BinaryTree.prototype.traverseInOrderIterative = function() {
var current = this._root,
s = [],
done = false;
while (!done) {
// Reach the left most Node of the current Node
if (current != null) {
// Place pointer to a tree node on the stack
// before traversing the node's left subtree
s.push(current);
s.push(current);
current = current.left;
} else {
if (s. length) {
current = s.pop();
console.log(current.value);
current = current.right;
} else {
done = true;
}
}
}
}
Kết quả của quá trình duyệt: [10, 41, 40, 42, 45, 50, 75].
Duyệt thứ tự trước (Post-order Traversal ):
duyệt thứ tự trước duyệt các node theo thứ tự sau: trái, phải, gốc.
Thứ tự duyệt:
BinaryTree.prototype.traversePostOrder = function() {
traversePostOrderHelper(this._root);
function traversePostOrderHelper(node) {
if (node.left) traversePostOrderHelper(node.left);
if (node.right) traversePostOrderHelper(node.right);
console.log(node.value);
}
}
BinaryTree.prototype.traversePostOrderIterative = function() {
// Create two stacks
var s1 = [], s2 = [];
// Push root to first stack
s1.push(this._root);
//# Run while first stack is not empty
while (s1.length) {
// Pop an item from s1 and append it to s2
var node = s1.pop();
s2.push(node);
// Push left and right children of removed item to s1
if (node.left) s1.push(node.left);
if (node.right) s1.push(node.right);
}
// Print all elements of second stack
while (s2.length) {
var node = s2.pop();
console.log(node.value);
}
}
kết quả in: [10, 40, 41, 45, 75, 50, 42].
kiểu duyệt này hay còn được biết đến như duyệt theo bề ngang của cây ( breadth first search (BFS) ):
BinaryTree.prototype.traverseLevelOrder = function() {
// Breath first search
var root = this._root, queue = [];
if (!root) return;
queue.push(root);
while (queue.length) {
var temp = queue.shift();
console.log(temp.value);
if (temp.left) queue.push(temp.left);
if (temp.right) queue.push(temp.right);
}
}
Kết quả: [42, 41, 50, 10, 40, 45, 75].
– khi cần thao tác với root trước dùng pre-order traversal
– khi cần thao tác với lá trước dùng post-order traversal
– khi muốn làm phẳng cây dùng in-order traversal
Độ phức tạp về thời gian cho việc duyệ là O(n) : duyệt qua tất cả các node.
Cây tìm kiếm nhị phân: (binary search trees)
Binary search trees (BSTs) cũng có hai con trái và phải, tuy nhiên trong Binary search trees con trái nhỏ hơn bố mẹ, con phải lớn hơn bố mẹ. BSTs có cấu trúc này bởi vì những thuộc tính này cho phép tìm kiếm, chèn, xóa phần tử xác định với độ phức tạp về thời gian O(log2(n)).
Binary search trees có một node gốc được khởi tạo với null,function BinarySearchTree(){
this._root = null;
}
Chèn:
Chèn trong BST bao gồm một vài bước, đầu tiên nếu root là rỗng, root trở thành root mới ngước lại một vòng lặp while được dùng để duyệt BST cho đến khi điều kiện bên phải được bắt gặp, tại mỗi vòng lặp sẽ kiểm tra xem ở đó node mới là lớn hơn hay nhỏ hơn root hiện tại.BinarySearchTree.prototype.insert = function(value) {
var thisNode = {left: null, right: null, value: value};
if(!this._root){
//if there is no root value yet
this._root = thisNode;
}else{
//loop traverse until
var currentRoot = this._root;
while(true){
if(currentRoot.value>value){
//let's increment if it's not a null and insert if it is a null
if(currentRoot.left!=null){
currentRoot = currentRoot.left;
}else{
currentRoot.left = thisNode;
break;
}
} else if (currentRoot.value < value) {
//if bigger than current, put it on the right
//let's increment if it's not a null and insert if it is a null
if(currentRoot.right!=null){
currentRoot = currentRoot.right;
}else{
currentRoot.right = thisNode;
break;
}
}else {
//case that both are the same
break;
}
}
}
}
độ phức tạp về thời gian cho cây cân bằng (có số node trái phải bằng nhau): O(log2(n))
cho cây không cân bằng: O(n)
Xóa:
Thuật toán này làm việc bằng cách duyệt xuống bên dưới cây để tìm kiếm các node đặc biệt với giá trị cụ thể, khi node được tìm thấy có 3 trường hợp có thể:
– node không có con: xóa node và trả về null
– có một con: xóa node, node con thay thế node cha.
– node có hai con: tìm node con bên trái lớn nhất hoặc tìm node con bên phải nhỏ nhất để thay thế node đó.BinarySearchTree.prototype.remove = function(value) {
return deleteRecursively(this._root, value);
function deleteRecursively(root, value) {
if(!root) {
return null;
} else if (value < root.value) {
root.left = deleteRecursively(root.left, value);
} else if (value > root.value) {
root.right = deleteRecursively(root.right, value);
} else {
//no child
if (!root.left && !root.right) {
return null; // case 1
} else if (!root.left) { // case 2
root = root.right;
return root;
} else if (!root.right) { // case 2
root = root.left;
return root;
} else{
var temp = findMin(root.right); // case 3
root.value = temp.value;
root.right = deleteRecursively(root.right, temp.value);
return root;
}
}
return root;
}
function findMin(root) {
while (root.left) {
root = root.left;
}
return root;
}
}
Độ phức tạp về thời gian cho cây cân bằng: O(log2(n))
Cây không cân bằng: O(n)
Tìm kiếm:
Tìm kiếm có thể sử dụng thuộc tính con bên trái của node BST là luôn luôn nhỏ hơn cha mẹ và con bên phải của node BST là luôn luôn lớn hơn cha mẹ. Duyệt cây có thể được hoàn thành bằng việc kiểm tra xem ở đó node gốc hiện tại là nhỏ hơn hay lớn hơn giá trị được tìm kiếm, nếu node root hiện tại là nhỏ hơn con phải sẽ được duyệt, ngược lại con trái sẽ được duyệt.BinarySearchTree.prototype.findNode = function(value) {
var currentRoot = this._root,
found = false;
while (currentRoot) {
if (currentRoot.value > value) {
currentRoot = currentRoot.left;
} else if (currentRoot.value < value) {
currentRoot = currentRoot.right;
} else {
//we've found the node
found = true;
break;
}
}
return found;
}
var bst1 = new BinarySearchTree();
bst1.insert(1);
bst1.insert(3);
bst1.insert(2);
bst1.findNode(3); // true
bst1.findNode(5); // false
độ phức tạp tìm kiếm trên cây cân bằng: O(log2(n))
cây không cân bằng: O(n)
Cây AVL:
cây AVL là cây nhị phân mà bản thân nó tự cân bằng. Một cây AVL giữ chiều cao của BST là nhỏ nhất và đảm bảo độ phức tạp về thời gian lag O(log2(n)) cho tìm kiếm, chèn và xóa. Code mô tả AVL tree:function AVLTree (value) {
this.left = null;
this.right = null;
this.value = value;
this.depth = 1;
}
chiều cao của cây AVL được dựa trên chiều cao của con và có thể được tính toán sử dụng khối mã sau:AVLTree.prototype.setDepthBasedOnChildren = function() {
if (this.node == null) {
this.depth = 0;
} else {
this.depth = 1;
}
if (this.left != null) {
this.depth = this.left.depth + 1;
}
if (this.right != null && this.depth <= this.right.depth) {
this.depth = this.right.depth + 1;
}
}
Xoay đơn:
cây AVL xoay con để duy trì cân bằng sau khi chèn.
Xoay trái:
Node con của 40, node 45 và 47 làm chiều cao không cân bằng, làm node cha trong cây BST
để thực hiện xoay trái đầu tiên lấy con trái đầu tiên và lưu lại nó, đây là con trái gốc, trở thành node cha.AVLTree.prototype.rotateLL = function() {
var valueBefore = this.value;
var rightBefore = this.right;
this.value = this.left.value;
this.right = this.left;
this.left = this.left.left;
this.right.left = this.right.right;
this.right.right = rightBefore;
this.right.value = valueBefore;
this.right.getDepthFromChildren();
this.getDepthFromChildren();
}
xoay phải:
cài đặt:AVLTree.prototype.rotateRR = function() {
// the right side is too long => rotate from the right (_not_ rightwards)
var valueBefore = this.value;
var leftBefore = this.left;
this.value = this.right.value;
this.left = this.right;
this.right = this.right.right;
this.left.right = this.left.left;
this.left.left = leftBefore;
this.left.value = valueBefore;
this.left.updateInNewLocation();
this.updateInNewLocation();
}
Xoay đôi:
nếu một cây AVL vẫn không cân bằng sau khi xoay, nó phải xoay hai lần cho cân bằng.
xoay phải trái:
Xoay trái phải:
Cây cân bằng:
để kiểm tra sự cân bằng của cây AVL đơn giản kiểm tra chiều cao của con trái và phải, nếu chiều cao không cần bằng cần xoay, khi trái lớn hơn phải thì xoay trái, nếu phải lớn hơn trái thì xoay phải:AVLTree.prototype.balance = function() {
var ldepth = this.left == null ? 0 : this.left.depth;
var rdepth = this.right == null ? 0 : this.right.depth;
if (ldepth > rdepth + 1) {
// LR or LL rotation
var lldepth = this.left.left == null ? 0 : this.left.left.depth;
var lrdepth = this.left.right == null ? 0 : this.left.right.depth;
if (lldepth < lrdepth) {
// LR rotation consists of a RR rotation of the left child
this.left.rotateRR();
// plus a LL rotation of this node, which happens anyway
}
this.rotateLL();
} else if (ldepth + 1 < rdepth) {
// RR or RL rorarion
var rrdepth = this.right.right == null ? 0 : this.right.right.depth;
var rldepth = this.right.left == null ? 0 : this.right.left.depth;
if (rldepth > rrdepth) {
// RR rotation consists of a LL rotation of the right child
this.right.rotateLL();
// plus a RR rotation of this node, which happens anyway
}
this.rotateRR();
}
}
Chèn:
chèn trong AVL BST cũng giống chèn trong BST ngoại trừ rằng khi được chèn, cha phải cân bằng con của nó và set right depth.AVLTree.prototype.insert = function(value) {
var childInserted = false;
if (value == this.value) {
return false; // should be all unique
} else if (value < this.value) {
if (this.left == null) {
this.left = new AVLTree(value);
childInserted = true;
} else {
childInserted = this.left.insert(value);
if (childInserted == true) this.balance();
}
} else if (value > this.value) {
if (this.right == null) {
this.right = new AVLTree(value);
childInserted = true;
} else {
childInserted = this.right.insert(value);
if (childInserted == true) this.balance();
}
}
if (childInserted == true) this.setDepthBasedOnChildren();
return childInserted;
}
độ phức tạp về thời gian: O(nlog2(n))
độ phức tạp về không gian: O(nlog2(n))
xóa:
AVL BST là một kiểu BST và do đó hàm xóa là giống nhau
sử dụng:
var avlTest = new AVLTree(1,”);
avlTest.insert(2);
avlTest.insert(3);
avlTest.insert(4);
avlTest.insert(5);
avlTest.insert(123);
avlTest.insert(203);
avlTest.insert(2222);
console.log(avlTest);
kết quả:
So sánh với cấu trúc dữ liệu khác việc tìm kiếm nhanh hơn linked list, array, stack và queue. Binary search là tuyệt với cho tìm kiếm, tuy nhiên chèn và xóa là chậm với độ phức tạp O(log2(n)) thay vì O(1) như stack hoặc queue, hơn nữa sẽ là O(n) khi cây không cân bằng, để đảm bảo cây cân bằng như cây đỏ đen hoặc cây AVL nên được sử dụng để có độ phức tạp logarit về thời gian.
Bài viết sau mình sẽ giới thiệu về đồ thị các loại thuật toán và ứng dụng của nó trong thực tiễn.