Skip to main content

· One min read

Trong bài viết này mình sẽ hướng dẫn cách sử dụng Pixi.js, Pixi-Viewport để tạo bản đồ sử dụng trong game Pixelland

  • Mạng lưới kẻ ô (grid)
  • Zoom và pan
  • Minimap
  • Fullscreen

Tạo map với pixi-viewport

· One min read
  • Contract Solidity khi dịch ra bytecode không được quá 24kb nếu không giao dịch deploy contract sẽ bị reject.

  • EVM - Etherium Virtual Machine là chương trình thực thi bytecode (sau khi được dịch ra từ Solidity hay Rust).

  • Thư viện (Library) dùng trong contract sẽ đc compile và deploy ra 1 địa chỉ riêng khác với địa chỉ deploy contract. Sau đó trong contract bytecode, ở các vị trí gọi đến hàm public của thư viện sẽ được link đến địa chỉ deploy của thư viện và gọi hàm bằng cách sử dụng opcode delegatecall của EVM.

  • Đối với các hàm internal của thư viện được dùng trong contract, bytecode của hàm sẽ được nhúng trực tiếp vào trong contract, và contract gọi đến hàm bằng cách dùng opcode JUMP giống như gọi các hàm internal bên trong contract (khác với việc sử dụng delagatecall đối với hàm public của thư viện). Lưu ý là chỉ những hàm internal được gọi mới được nhúng vào contract bytecode (maximum 24kb).

  • Selector

bytes4(keccak256('supportsInterface(bytes4)')) == 0x01ffc9a7

· 13 min read

Smartcontract trên ETH hay các hệ tương thích EVM (Etherium Virtual Machine) như BSC hay Avax có tính chất immutable tức là code khi đã được deploy lên 1 địa chỉ xác định thì không thể thay đổi. Điều này giúp tăng tính minh bạch và việc audit hoạt động của smartcontract thuận tiện hơn cho người dùng. Tuy nhiên lại có 1 điểm bất lợi rõ ràng là code không thể thay đổi để sửa lỗi hay thêm tính năng mới cho smartcontract, mà đây lại là những công việc rất quan trọng và diễn ra liên tục trong quá trình phát triển sản phẩm.

· 11 min read

ERC20 là chuẩn dành cho những đồng token có tính chất giống hệt nhau (fungible token), giống như 1 đồng USD có giá trị hoàn toàn tương đương với 1 đồng USD bất kỳ nào khác. Đối với các loại tài sản có tính chất riêng biệt độc nhất (Non Fungible Token - NFT) như mỗi mảnh đất, mỗi vật phẩm, nhân vật trong game..., chúng ta có chuẩn ERC721 để số hóa các loại tài sản như vậy trên Blockchain.

· 12 min read

Token ERC20 là 1 trong những ứng dụng Blockchain cơ bản và phổ biến nhất hiện nay.

Các khái niệm cơ bản

Để hiểu cách thức hoạt động và cài đặt 1 đồng token trên mạng lưới Blockchain trước hết ta nhắc lại sơ qua các khái niệm sau

  • Blockchain
  • Transaction
  • Account
  • Smartcontract
  • ERC20

· 20 min read

Cây đỏ đen (red black tree) là cây nhị phân tìm kiếm được ràng buộc thêm bởi 1 số điều kiện (constraint) để đảm bảo cây luôn ở trạng thái tương đối cân bằng (độ dài giữa các nhánh cây không chênh lệch nhau quá lớn), nhằm tối đa hóa hiệu quả các thao tác tìm kiếm và lưu trữ trên cây.

1 dạng khác của cây nhị phân tự cân bằng là cây AVL, tuy nhiên điều kiện cân bằng của cây đỏ đen được thiết kế lỏng hơn so với cây AVL. Ở cây AVL độ dài 2 nhánh cây chênh nhau không quá 1 đơn vị thì ở cây đỏ đen 1 nhánh cây có độ dài không quá 2 lần nhánh còn lại (với mọi nút). Do tính chất này trong trường hợp thực hiện nhiều lần các thao tác thêm và xóa với cây đỏ đen sẽ hiệu quả hơn so với cây AVL vì không phải tái cấu trúc cây quá nhiều lần.

Tính chất cây đỏ đen

  1. Mọi nút đều có thuộc tính là đỏ hoặc đen.
  2. Nút gốc là nút đen.
  3. Tất cả nút NULL là nút đen.
  4. Nếu 1 nút là đỏ thì tất cả nút con của nó phải là đen, hay nói cách khác không có 2 nút đỏ liên tiếp trên 1 đường đi từ gốc đến lá.
  5. Với mọi đường đi từ gốc đến NULL, số nút đen là bằng nhau.

Ở đây 2 tính chất logic chính để tạo nên tính cân bằng cho cây đỏ đen là tính chất 4 và 5. Ta sử dụng 2 tính chất này để chứng minh tính cân bằng của cây đỏ đen.

Tính cân bằng của cây đỏ đen

Theo tính chất 5, với mọi đường đi từ gốc đến NULL số nút đen là bằng nhau, gọi số nút đen này là bh (black-height, không tính NULL). Trong trường hợp không có nút đỏ nào ta có cây nhị phân hoàn hảo (Perfect Binary Tree) có tổng số nút n = 2^bh - 1. Trong trường hợp có thêm các nút đỏ và số nút đen giữ nguyên, ta có tổng số nút n >= 2^bh - 1.

Gọi độ cao cây là h, theo tính chất 4 do không có 2 nút đỏ liên tiếp trên đường đi từ gốc đến NULL nên ta có bh >= h/2, vì nếu bh < h/2 ta bắt buộc phải có 2 nút đỏ liên tiếp.

Tổng hợp 2 ý trên ta có n >= 2^bh -1 >= 2^(h/2) - 1. Suy ra: n + 1 >= 2^(h/2) => log(n + 1) >= h/2 hay h <= 2log(n + 1).

Suy ra độ phức tạp tính toán của cây nhị phân là O(h) hay chính là O(logn).

Các thao tác tái cấu trúc cây

Ngoài các thao tác chính của cây nhị phân tìm kiếm (Thêm, xóa), chúng ta sử dụng các công cụ sau để tái cấu trúc cho cây khi cần thiết.

Xoay trái (Left-rotation) và xoay phải (Right-rotation)

Từ trạng thái 1 -> trạng thái 2 ta có thao tác xoay trái đối với x. Ngược lại từ 2 -> 1 ta có thao tác xoay phải đối với y. Ta kiểm tra tính chất của cây nhị phân tìm kiếm hoàn toàn đảm bảo trong cả 2 trường hợp (các nút trái < gốc < các nút phải).

(1/2)

Phần cây xoay có thể là con trái hoặc con phải của P.

Đổi màu (Flip-color)

Đổi màu 1 nút từ đỏ thành đen hoặc ngược lại.

Các thao tác

Cây đỏ đen có các thao tác thêm, xóa, tìm kiếm, tìm phần tử trước, phần tử sau, duyệt... giống như ở cây nhị phân thông thường. Ở đây ta đi vào phần cài đặt 2 thao tác chính mà đòi hỏi cây đỏ đen tự tái cấu trúc nó để đạt được sự cân bằng:

  • Thêm (Insert)
  • Xóa (Delete)
tip

Trước khi đi vào phần cài đặt cụ thể ta chú ý 2 điều sau để nắm được logic của thuật toán:

  • Nút đỏ mang ý nghĩa là cây đang lệch về phía nhánh cây chứa nó.
  • Nếu T là cây đỏ đen thì mọi cây con của T đều thỏa mãn tính chất 4 và 5.

Thao tác thêm (Insert)

Trước hết thêm phần tử vào cây như ở cây nhị phân tìm kiếm thông thường và gán cho nút mới này màu đỏ. Sau đó ý ta kiểm tra xem liệu có 2 phần tử màu đỏ liên tiếp xảy ra vì thao tác này không (2 nút đỏ liên tiếp mang ý nghĩa là việc thêm phần tử làm cây lệch nhiều hơn mức cho phép về phía đó). Nếu có ta sửa nó bằng cách vận dụng các thao tác xoay cây và đổi màu.

Gọi cây hiện tại T, nút mới thêm K, nút cha của nút mới thêm P, nút ông (grandparent) G và nút chú (uncle - nút anh em của nút cha) U. Xét các trường hợp sau:

Case 1: K là gốc (không tồn tại nút cha P)

Nếu K là gốc và màu đỏ, ta chuyển màu K thành đen. Trường hợp này độ cao màu đen bh của cây tăng thêm 1.

Chú ý thuật toán gọi vào đây ở 1 trong 2 trường hợp:

  • Thêm K vào cây rỗng
  • Gọi đệ qui từ dưới lên ở trường hợp 3.1 (được nhắc đến ở dưới)

Case 2: Nút cha P màu đen

Nếu nút cha P của K màu đen, và K được set là đỏ nên thao tác thêm này không làm ảnh hưởng tính chất cây đỏ đen nên không phải làm gì thêm.

Case 3: Nút cha P màu đỏ

Khi này ta có 2 nút đỏ liên tiếp PK. P màu đỏ suy ra nút ông G màu đen vì T đảm bảo tính chất cây đỏ đen trước khi thêm K. Để sửa tình huống này ta cần xét nút chú U là đỏ hay đen.

Case 3.1 P màu đỏ và U cũng màu đỏ: tình huống này ta đổi màu P thành đen, U thành đen và G thành đỏ. Khi này số nút đen của 2 nhánh không đổi và 2 nút đỏ liên tiếp của phần cây con GPUK được sửa.

(1/2)

Do G chuyển màu từ đen sang đỏ có khả năng gặp 1 nút đỏ liên tiếp ở trên, ta tiếp tục thực hiện thao tác kiểm tra và sửa nếu cần thiết lên trên với G đóng vai trò là K (gọi đệ qui lặp lại từ case 1 đối với nút ông G).

Case 3.2 P màu đỏ và U màu đen (hoặc NULL): trường hợp này ta có thể giải quyết bằng 1 hoặc 2 phép xoay cây tùy thuộc vào PK là nút con trái hay phải.

Case 3.2.1 P là con phải của G, K là con phải của P:

  • Thực hiện phép xoay trái đối với G.
  • Đổi màu P thành đen, G sang đỏ.
(1/2)

Case 3.2.2 P là con phải của G, K là con trái của P:

  • Thực hiện phép xoay phải đối với P.
  • Trở về case 3.2.1 (với KP đổi vai trò cho nhau).
(1/2)

Case 3.2.3 P là con trái của G, K là con trái của P, trường hợp này ngược lại với 3.2.1:

  • Thực hiện phép xoay phải đối với G.
  • Đổi màu P thành đen, G sang đỏ.
(1/2)

Case 3.2.4 P là con trái của G, K là con phải của P, trường hợp này ngược lại với 3.2.2:

  • Thực hiện phép xoay trái đối với P.
  • Trở về case 3.2.3 (với KP đổi vai trò cho nhau).
(1/2)

Tóm tắt thuật toán insert

  • Thêm nút mới như ở cây nhị phân thông thường và gán màu của nút mới là đỏ.
  • Nếu nút mới thêm là gốc (không có cha) thì chuyển màu đỏ sang đen.
  • Nếu nút cha màu đen ko cần làm gì thêm.
  • Nếu nút cha cũng là đỏ sửa tình huống có 2 nút đỏ liên tiếp bằng cách xem nhánh đối diện:
    • Nếu nút chú màu đỏ ta đổi màu nút cha và chú thành đen, nút ông thành đỏ rồi tiếp tục gọi đệ qui lên trên (đối với nút ông) để sửa nút đỏ này nếu cần.
    • Nếu nút chú là màu đen ta có thể sửa sự lệch của cây con đang xét bằng phép xoay cây sang phía nhánh của nút chú.

Thao tác xóa (Delete)

Trước hết ta làm theo các bước xóa như ở trong cây nhị phân tìm kiếm thông thường để đưa về trường hợp xóa nút x là nút lá hoặc chỉ có 1 con (xem phần xóa trong bài về cây nhị phân tìm kiếm).

Ý tưởng của thuật toán là kiểm tra cây đang lệch về phía nào bằng cách xem nút đỏ đang nằm ở đâu quanh chỗ nút muốn xóa và cố gắng chuyển chỗ lệch đó về phía nhánh của phần tử này. Hay nói cách khác, tìm cách chuyển màu của nút muốn xóa thành đỏ mà vẫn giữ tính chất cây đỏ đen bằng cách vận dụng các thao tác xoay cây và đổi màu, khi đó ta dễ dàng xóa phần tử mà vẫn giữ được tính cân bằng của cây.

Gọi S là nút anh em (sibling) của xP là nút cha của x. Xét các trường hợp sau:

Case 1 x là nút đỏ

Trường hợp này ta xóa x như đối với cây nhị phân tìm kiếm thông thường vì nó ko làm ảnh hưởng đến tính chất 4 và 5 được nhắc ở trên.

Case 2 x là nút đen và có nút con là đỏ

Ta thay x bằng nút con đỏ của nó và đổi màu nút con đỏ thành đen. Thay 1 nút đen bằng 1 nút đen khác tính chất cây đỏ đen được bảo toàn.

(Trường hợp x là nút đen có 1 nút con NULL và 1 nút con là đen khác NULL ko tồn tại vì vi phạm tính chất 5).

Case 3 x là nút màu đen

Khi x là nút màu đen, ta tìm cách chuyển x thành đỏ bằng các thao tác xoay cây và đổi màu. Để giản lược ta xét trường hợp x là con trái với 4 trường hợp con sau (với trường hợp x là con phải ta làm giống hệt nhưng ngược lại động tác xoay):

Case 3.1 S là nút đen, nút con phải của S là đỏ.

Trường hợp này nút con trái của S, nút cha P có thể là đen hoặc đỏ đều được.

  • Thực hiện phép xoay trái đối với P.
  • Gán màu của S là màu hiện tại của P.
  • Gán màu của P là đen.
  • Gán màu con phải của S là đen.
  • Gán màu của x là đỏ.

Minh họa, với màu hồng nghĩa là màu đỏ hoặc đen đều được:

(1/3)

Trên hình minh họa ta nhận thấy nếu trạng thái 1 được đảm bảo tính chất cây đỏ đen thì trạng thái 3 cũng đảm bảo tính chất này.

Trạng thái 1:

(..)
(B){"t":"P","c":"pink"}
(A){"c":"black","t":"x"}(D){"c":"black","t":"S"}
(C){"p":"D","c":"pink"}(E){"p":"D","c":"red"}

Trạng thái 3:

(..)
(D){"c":"pink","t":"S"}
(B){"t":"P","c":"black"}(E){"c":"black"}
(A){"c":"red","t":"x"}(C){"c":"pink"}

Ta thấy nút x được chuyển từ màu đen sang đỏ, có nút cha màu đen, xem xét khả năng có thể dẫn đến 2 nút đỏ liên tiếp không:

  • Nếu x ban đầu là nút lá màu đen, trong trường hợp này đổi sang đỏ không tạo thành 2 nút đỏ liên tiếp.
  • Nếu là trường hợp gọi đệ qui từ dưới lên nhằm chuyển x thành đỏ, ta chỉ gọi đến đoạn này trong trường hợp x là đen và cả 2 con của x cũng là đen (cụ thể là trường hợp 3.3.2 ở dưới). Nên việc đổi màu x sang đỏ cũng không tạo thành 2 nút đỏ liên tiếp.

Như vậy điều kiện không có 2 nút đỏ liên tiếp được đảm bảo, xét về số nút đen:

  • ..BA.. trạng thái 1 = ..DBA.. trạng thái 3
  • ..BDC.. trạng thái 1 = ..DBC.. trạng thái 3
  • ..BDE.. trạng thái 1 = ..DE.. trạng thái 3

Như vậy nếu trạng thái 1 đảm bảo tính chất về số nút đen, thì trường hợp 3 cũng đảm bảo tính chất này. Các case sau ta cũng phân tích tương tự để thấy tính chất cây đỏ đen được đảm bảo sau các thao tác tái cấu trúc cây.

Case 3.2 S là nút đen, nút con trái của S là đỏ.

Ta chỉ xét trường hợp nút con phải của S là đen (hoặc NULL), nút cha P có thể là đen hoặc đỏ đều được.

  • Đổi màu nút S sang đỏ, nút con trái của S sang đen.
  • Thực hiện động tác xoay phải đối với S.
  • Ta có cây trở về trường hợp 3.1 với con trái S (lúc chưa xoay) đóng vai trò là nút S mới, thực hiện tiếp các bước giống như ở 3.1.
(1/4)
(..)
(B){"c":"pink","t":"P"}
(A){"c":"black","t":"x"}(D){"c":"black","t":"S"}
(C){"c":"red","p":"D"}(E){"p":"D","c":"black"}

(..)
(B){"c":"pink","t":"P"}
(A){"c":"black","t":"x"}(C){"c":"black","t":"new S"}
(F){"p":"C","c":"pink","t":"C's left child"}(D){"c":"red","t":"S","p":"C"}

(..)
(C){"c":"black","t":"new S"}
(B){"c":"pink","t":"P"}(D){"c":"red","t":"S"}
(A){"c":"black","t":"x"}(F){"c":"pink"}

(..)
(C){"c":"pink","t":"new S"}
(B){"c":"black","t":"P"}(D){"c":"black","t":"S"}
(A){"c":"red","t":"x"}(F){"c":"pink"}

Case 3.3 S là nút đen, cả 2 con của S là đen

Case 3.3.1 nếu nút cha P là đỏ

  • Đổi màu P sang đen.
  • Đổi màu S sang đỏ
  • Đổi màu x sang đỏ
(1/2)
(B){"c":"red","t":"P"}
(A){"c":"black","t":"x"}(D){"c":"black","t":"S"}
(C){"c":"black","p":"D"}(E){"c":"black","p":"D"}

(B){"c":"black","t":"P"}
(A){"c":"red","t":"x"}(D){"c":"red","t":"S"}
(C){"c":"black","p":"D"}(E){"c":"black","p":"D"}

Case 3.3.2 nếu nút cha P là đen

Trường hợp này nhánh cây con đang xét toàn là đen ta gọi đệ qui lên trên nhằm chuyển phần lệch về phía cây con đang xét (đổi màu nút cha P sang đỏ).

  • Lặp lại từ đầu case 3 với nhiệm vụ đổi màu nút cha P sang đỏ (P đóng vai trò là nút x mới).
  • Với nút cha P đỏ, tiếp tục thực hiện các bước như ở 3.3.1.
(1/3)
(B){"c":"black","t":"P"}
(A){"c":"black","t":"x"}(D){"c":"black","t":"S"}
(C){"c":"black","p":"D"}(E){"c":"black","p":"D"}

(B){"c":"red","t":"P"}
(A){"c":"black","t":"x"}(D){"c":"black","t":"S"}
(C){"c":"black","p":"D"}(E){"c":"black","p":"D"}

(B){"c":"black","t":"P"}
(A){"c":"red","t":"x"}(D){"c":"red","t":"S"}
(C){"c":"black","p":"D"}(E){"c":"black","p":"D"}

Case 3.4 S là nút màu đỏ

Lúc này cả 2 con của S là màu đen (theo tính chất 4)

  • Thực hiện thao tác xoay trái đối với P.
  • Đổi màu S thành đen, P thành đỏ.
  • Lúc này bài toán trở về 3.1, 3.2 hoặc 3.3.1 (x màu đen, nút cha P màu đỏ và S mới màu đen).
(1/3)
(..)
(B){"c":"black","t":"P"}
(A){"c":"black","t":"x"}(D){"c":"red","t":"S"}
(C){"c":"black","p":"D"}(E){"c":"black","p":"D"}

(..)
(D){"c":"red","t":"S"}
(B){"c":"black","t":"P"}(E){"c":"black"}
(A){"c":"black","t":"x"}(C){"c":"black"}

(..)
(D){"c":"black","t":"S"}
(B){"c":"red","t":"P"}(E){"c":"black"}
(A){"c":"black","t":"x"}(C){"c":"black","t":"new S"}

Kết thúc case 3: sau khi thành công chuyển màu của x sang đỏ, thực hiện xóa x (x khi này là nút lá).

Tóm tắt thuật toán xóa

  • Thực hiện các bước xóa ban đầu giống với cây nhị phân tìm kiếm thông thường, đưa về TH xóa x là nút lá hoặc chỉ có 1 con (ít nhất 1 nút con của x là NULL).
  • Nếu nút cần xóa x là màu đỏ bỏ qua các bước sau để đến bước cuối cùng (xóa x khỏi cây).
  • Nếu x là màu đen ta tìm cách chuyển màu x sang đỏ, hay nói cách khác là chuyển dịch sự lệch của cây sang nhánh muốn xóa (đỏ tượng trưng cho nhánh cây dài hơn). Ta tìm nút đỏ lần lượt ở các vị trí sau (đến khi tìm đc thì dừng):
    • Con của x.
    • Nút anh em (sibling) của x.
    • Con của nút anh em.
    • Cha của x.
  • Nếu không tìm thấy đỏ ở các vị trí trên, ta tìm cách chuyển màu nút cha của x sang màu đỏ (bằng cách gọi đệ quy bước 2 nhưng là đối với cha của x).
  • Khi đã tìm được đỏ ở 1 trong các vị trí này có thể áp dụng các biện pháp xoay cây và đổi màu để chuyển x sang đỏ mà vẫn giữ được tính chất của cây (các bước cụ thể được nêu ở trên).
  • Xóa x khỏi cây như ở cây nhị phân tìm kiếm thông thường.

Minh họa

export interface RedBlackNode {
value: number
color: 0 | 1
parent: RedBlackNode | null
left: RedBlackNode | null
right: RedBlackNode | null
}

function createNode(value: number): RedBlackNode {
return {
value,
color: 1,
parent: null,
left: null,
right: null
}
}

export class RedBlackTree {
root: RedBlackNode | null = null

insert(value: number) {
console.log('insert', value)
const k = insertNode(this.root, value)
if (!k) return
if (!this.root) {
this.root = k
}

this.fixInsert(k)
}

remove(value: number) {
const delNode = searchNode(this.root, value)
if (!delNode) return

// find actual removed node
let altNode: RedBlackNode | null = null
if (delNode.left && delNode.right) {
altNode = findMinNode(delNode.right)
}

const xNode = altNode || delNode

// fix the node to be deleted
this.fixDelete(xNode)

// override delnode if different, then delete
delNode.value = xNode.value
this.deleteNode(xNode)
}

private rotateLeft(x: RedBlackNode): void {
if (!x) return
const p = x.parent
const y = x.right
if (!y) return
const b = y.left

// update b
if (b) b.parent = x

// update x
x.parent = y
x.right = b

// update y
y.parent = p
y.left = x

// update p
if (p) {
// not rotate root
if (p.left === x) {
p.left = y
} else {
p.right = y
}
} else {
// rotate root
this.root = y
}
}

private rotateRight(y: RedBlackNode): void {
if (!y) return
const p = y.parent
const x = y.left
if (!x) return
const b = x.right

// update b
if (b) b.parent = y

// update y
y.parent = x
y.left = b

// update x
x.parent = p
x.right = y

// update p
if (p) {
// not rotate root
if (p.left === y) {
p.left = x
} else {
p.right = x
}
} else {
// rotate root
this.root = x
}
}

private deleteNode(node: RedBlackNode) {
if (!node) return
if (node.left && node.right) return

const child = node.left || node.right
const p = node.parent
if (p) {
if (p.left === node) {
p.left = child
} else {
p.right = child
}
if (child) {
child.parent = p
}
} else {
this.root = child
if (child) {
child.parent = null
}
}
}

// fix 2 consecutive red nodes (mainly)
private fixInsert(k: RedBlackNode) {
const p = k.parent
if (!p) {
// root node, make it black
k.color = 0
return
}

const isNodeLeft = p.left === k

if (!isRed(p)) {
// Case 2: nothing to do if parent is black
return
}

const g = p.parent
if (!g) return

const isParentLeft = g.left === p
const u = isParentLeft ? g.right : g.left

if (u && isRed(u)) {
p.color = 0
u.color = 0
g.color = 1
this.fixInsert(g)
return
}

// u is black

if (!isParentLeft) {
// p is right child
if (!isNodeLeft) {
// node is right child
this.rotateLeft(g)
p.color = 0
g.color = 1
} else {
// node is left child
this.rotateRight(p)
// repeat the above fix
this.fixInsert(p)
}
} else {
// p is left child
if (isNodeLeft) {
// node is left
this.rotateRight(g)
p.color = 0
g.color = 1
} else {
this.rotateLeft(p)
this.fixInsert(p)
}
}
}

// try to turn the node into red
private fixDelete(x: RedBlackNode) {
console.log('fix_Delete', x)
if (isRed(x)) {
return
}

// only 1 red child node
if (!x.left || !x.right) {
const child = x.left || x.right
if (child && isRed(child)) {
x.color = 1
child.color = 0
return
}
}

// x's children are black (possibly NULL)

const p = x.parent
// if x is root change color to red
// (to remove or swap again after recursive call)
if (!p) {
// TODO document this case
x.color = 1
return
}

const isNodeLeft = p.left === x
// sibling

if (isNodeLeft) {
const s = p.right
// this case not exist (break attribute 5)
if (!s) return

// s is black
if (!isRed(s)) {
if (s.right && isRed(s.right)) {
// 3.1, s.right is red
this.rotateLeft(p)
s.color = p.color
p.color = 0
s.right.color = 0
x.color = 1 // done
} else if (s.left && isRed(s.left)) {
// 3.2, s.left is red
s.color = 1
s.left.color = 0
this.rotateRight(s)
// reduce to 3.1
this.fixDelete(x)
} else {
// 3.3, both s's children are black
if (isRed(p)) {
// 3.3.1
p.color = 0
s.color = 1
x.color = 1
} else {
// 3.3.2
// TODO check if P root do {...}
this.fixDelete(p)
// changed p into red, reduce to 3.3.1
this.fixDelete(x)
}
}
} else {
// 3.4
this.rotateLeft(p)
s.color = 0
p.color = 1
// reduce to 3.1, 3.2 or 3.3.1
this.fixDelete(x)
}
} else {
// mirror of above 3.* cases
const s = p.left
// this case not exist (break attribute 5)
if (!s) return
// s is black
if (!isRed(s)) {
if (s.left && isRed(s.left)) {
// mirror 3.1, s.left is red
this.rotateRight(p)
s.color = p.color
p.color = 0
s.left.color = 0
x.color = 1 // done
} else if (s.right && isRed(s.right)) {
// mirror 3.2, s.right is red
this.rotateLeft(s)
s.color = 1
s.right.color = 0
// reduce to mirror 3.1
this.fixDelete(x)
} else {
// mirror 3.3, both s's children are black
if (isRed(p)) {
// mirror 3.3.1
p.color = 0
s.color = 1
x.color = 1
} else {
// mirror 3.3.2
this.fixDelete(p)
// changed p into red, reduce to mirror 3.3.1
this.fixDelete(x)
}
}
} else {
// mirror 3.4
this.rotateRight(p)
s.color = 0
p.color = 1
// reduce to mirror 3.1, 3.2 or 3.3.1
this.fixDelete(x)
}
}
}
}

function insertNode(node: RedBlackNode | null, value: number): RedBlackNode | null {
if (!node) {
return createNode(value)
}

// no insert duplicate value
if (node.value === value) return null

const isGoLeft = value < node.value
const next = isGoLeft ? node.left : node.right

const k = insertNode(next, value)
if (!k) return null

if (!next) {
// just created k
k.parent = node
if (isGoLeft) {
node.left = k
} else {
node.right = k
}
}

return k
}

function isRed(node: RedBlackNode | null): boolean {
return node ? node.color === 1 : false
}

function searchNode(node: RedBlackNode | null, value: number): RedBlackNode | null {
if (!node) return null
if (node.value === value) return node
if (value < node.value) {
return searchNode(node.left, value)
}

return searchNode(node.right, value)
}

function findMinNode(node: RedBlackNode): RedBlackNode {
let n = node
while (n.left) n = n.left

return n
}

· 16 min read

B-Tree là cây tìm kiếm tự cân bằng và là dạng tổng quát của cây nhị phân tìm kiếm trong đó 1 node có thể có nhiều hơn 1 phần tử. Không như các cây tìm kiếm tự cân bằng khác như AVL tree hay Redblack tree được sử dụng chủ yếu trong bộ nhớ RAM, BTree được sinh ra do nhu cầu lưu trữ và tìm kiếm dữ liệu trên bộ nhớ cứng (hard disk).

· One min read
Sébastien Lorber
Yangshun Tay

Docusaurus blogging features are powered by the blog plugin.

Simply add Markdown files (or folders) to the blog directory.

Regular blog authors can be added to authors.yml.

The blog post date can be extracted from filenames, such as:

  • 2019-05-30-welcome.md
  • 2019-05-30-welcome/index.md

A blog post folder can be convenient to co-locate blog post images:

Docusaurus Plushie

The blog supports tags as well!

And if you don't want a blog: just delete this directory, and use blog: false in your Docusaurus config.