sử dụng con trỏ kép thay vì con trỏ đơn

Question

Tôi đang làm việc trên cây tìm kiếm nhị phân.

Vì vậy, đây là cấu trúc được sử dụng để đại diện cho các nút:

typedef struct TreeNode 
{ 
int num; 
struct TreeNode *left,*right; 
}TREENODE; 

Để chèn một nút trong cây Tôi đã sau phương pháp signatire

void InsertNode(TREENODE **root,int data); 

Trong các phương pháp trên tại sao chúng ta yêu cầu con trỏ đôi.Chúng tôi có thể sử dụng một con trỏ duy nhất!

Chúng tôi có sử dụng con trỏ kép để tránh trùng lặp không?

Answer 1

Không, điều này là cần thiết trong trường hợp tái cân bằng. Sau khi tái cân bằng gốc có thể được thay đổi.

Ok, tôi sẽ mở rộng. Con trỏ kép cho phép bạn sửa đổi con trỏ. Vậy gốc cây là gì trong trường hợp của bạn? Con trỏ đến TREENODE. Một số thao tác như tìm kiếm sẽ không bao giờ sửa đổi nó. Nhưng một số hoạt động có thể cần phải thay đổi nó để một nút khác trở thành gốc mới. Vì vậy, họ phải có quyền truy cập vào biến mà bạn sử dụng như là người chủ. Một ví dụ tại sao họ có thể cần nó là tái cân bằng, xem AVL trees.

Answer 2

Nếu chúng tôi cần con trỏ kép, thì chúng ta cần sửa đổi con trỏ trỏ đến.

Answer 3

Nó rất phụ thuộc vào cách bạn sử dụng cây. nếu cây nên giữ trên một số loại phân loại, do đó, chèn có thể thay đổi nút gốc, vì vậy bạn cần con trỏ đôi.

Answer 4

Không - bạn đang sử dụng điểm kép để bạn có thể sửa đổi con trỏ.

Answer 5

Sử dụng "Con trỏ kép" cho phép bạn thay đổi Nội dung của bộ nhớ <some_class>* giữ địa chỉ của. Vì vậy, về cơ bản chúng tôi bảo toàn trạng thái của vị trí bộ nhớ ngay cả khi có cuộc gọi chức năng bên ngoài. Sử dụng khác giống như cho ví dụ: char* (như Chuỗi), và char** (như mảng của chuỗi)

Bạn có thể tìm thấy câu trả lời của tôi trong một thread: Why use double pointer? or Why use pointers to pointers?