Finding yếu tố cuối cùng của một đống nhị phân

Question

trích dẫn Wikipedia:

Nó là hoàn toàn chấp nhận được để sử dụng một truyền thống cây nhị phân cấu trúc dữ liệu để thực hiện một đống nhị phân. Có một vấn đề với việc tìm kiếm các yếu tố liền kề vào mức độ cuối cùng trên đống nhị phân khi thêm một yếu tố có thể được giải quyết thuật toán ...

Bất kỳ ý tưởng về cách như vậy thuật toán có thể hoạt động?

Tôi không thể tìm thấy bất kỳ thông tin nào về vấn đề này, đối với hầu hết các đống nhị phân được triển khai bằng cách sử dụng mảng.

Bất kỳ trợ giúp đánh giá cao.

---

Gần đây, tôi đã đăng ký tài khoản OpenID và không thể chỉnh sửa bài đăng đầu tiên cũng như các câu trả lời nhận xét. Đó là lý do tại sao tôi trả lời qua câu trả lời này. Xin lỗi vì điều này.

---

trích dẫn Mitch Wheat:

@Yse: là câu hỏi của bạn "Làm thế nào để tìm yếu tố cuối cùng của một đống nhị phân"?

Vâng, đúng vậy. Hoặc để chính xác hơn, câu hỏi của tôi là: "Làm cách nào để tìm phần tử cuối cùng của một cụm nhị phân không dựa trên mảng nhị phân?".

trích dẫn Suppressingfire:

Có một số bối cảnh trong đó bạn hỏi câu hỏi này? (Ví dụ, là có một số vấn đề cụ thể bạn đang cố gắng giải quyết?)

Như đã trình bày ở trên, tôi muốn biết một cách tốt để "tìm ra yếu tố cuối cùng của một nhị phân không cho mảng dựa trên heap "cần thiết cho việc chèn và xóa các nút.

trích Roy:

Có vẻ như dễ hiểu nhất đối với tôi để chỉ cần sử dụng một nhị phân cấu trúc cây bình thường (sử dụng một pRoot và Node định nghĩa là [dữ liệu, pLeftChild, pRightChild]) và thêm hai con trỏ bổ sung (pInsertionNode và pLastNode). pInsertionNode và pLastNode sẽ được cập nhật trong suốt các chương trình con chèn và xóa để giữ chúng hiện tại khi dữ liệu thay đổi cấu trúc.Điều này cho O (1) truy cập vào cả hai chèn điểm và nút cuối cùng của cấu trúc.

Có, thao tác này sẽ hoạt động. Nếu tôi không nhầm, nó có thể là một chút khôn lanh để tìm nút chèn và nút cuối cùng, khi vị trí của họ thay đổi sang một cây con khác do xóa/chèn. Nhưng tôi sẽ thử.

trích dẫn Zach Scrivena:

Làm thế nào về thực hiện một chiều sâu-đầu tiên tìm kiếm ...

Vâng, đây sẽ là một cách tiếp cận tốt. Tôi cũng sẽ thử điều đó.

Tôi vẫn tự hỏi, nếu có cách "tính toán" vị trí của nút cuối cùng và điểm chèn. Chiều cao của một đống nhị phân với N nút có thể được tính toán bằng cách lấy nhật ký (của cơ số 2) của công suất nhỏ nhất của hai lớn hơn N. Có lẽ nó có thể tính toán số lượng các nút ở mức sâu nhất, quá. Sau đó, nó có thể có thể xác định làm thế nào heap đã được đi qua để đạt được điểm chèn hoặc nút để xóa.

Answer 1

Cách thực hiện depth-first search, truy cập vào con trái trước con phải để xác định chiều cao của cây. Sau đó, lá đầu tiên bạn gặp phải với độ sâu ngắn hơn, hoặc cha mẹ có con bị thiếu sẽ cho biết nơi bạn nên đặt nút mới trước khi "sủi bọt".

---

Phương pháp tìm kiếm theo chiều sâu (DFS) ở trên không cho rằng bạn biết tổng số nút trong cây. Nếu thông tin này là có sẵn, sau đó chúng ta có thể "zoom-in" một cách nhanh chóng đến nơi mong muốn, bằng cách sử dụng các thuộc tính của cây nhị phân hoàn chỉnh:

Hãy N là tổng số nút trong cây và H là chiều cao của cây.

Một số giá trị của (N, H) là (1,0), (2,1), (3,1), (4,2), ..., (7,2) , (8, 3). Công thức chung liên quan hai là H = ceil [log2 (N +1)] - 1. Bây giờ, đưa ra chỉ N, chúng tôi muốn đi qua từ gốc đến vị trí cho nút mới, trong số ít nhất các bước, nghĩa là không có bất kỳ "backtracking" nào. Đầu tiên chúng ta tính tổng số các nút M trong một cây nhị phân hoàn hảo chiều cao H = ceil [log2 (N +1)] - 1, đó là M = 2^(H +1) - 1.

Nếu N == M, sau đó cây của chúng tôi là hoàn hảo , và nút mới cần được thêm vào trong một cấp độ mới.Điều này có nghĩa rằng chúng ta có thể chỉ cần thực hiện một DFS (trái trước phải) cho đến khi chúng tôi nhấn đầu tiên lá; nút mới trở thành con trái của lá này. Kết thúc câu chuyện.

Tuy nhiên, nếu N < M, sau đó vẫn vacancies ở mức cuối cùng của cây của chúng tôi, và các nút mới nên được bổ sung vào chỗ trống bên trái. Số lượng nút đã ở cấp cuối cùng của cây của chúng tôi chỉ là (N - 2^H + 1). Điều này có nghĩa là nút mới mất vị trí X = (N - 2^H + 2) từ bên trái, ở cấp độ cuối cùng.

Bây giờ, để đến đó từ gốc, bạn sẽ cần phải thực hiện rẽ chính xác (L vs R) ở mỗi cấp để bạn kết thúc tại chỗ X ở cấp độ cuối cùng. Trong thực tế, bạn sẽ xác định lượt với một tính toán nhỏ ở mỗi cấp. Tuy nhiên, tôi nghĩ rằng bảng sau đây cho thấy bức tranh lớn và các mô hình có liên quan mà không bị sa lầy trong số học (bạn có thể nhận ra đây là một hình thức arithmetic coding cho một phân bố đều):

0 0 0 0 0 X 0 0 <--- represents the last level in our tree, X marks the spot! 
     ^
L L L L R R R R <--- at level 0, proceed to the R child 
L L R R L L R R <--- at level 1, proceed to the L child 
L R L R L R L R <--- at level 2, proceed to the R child 
     ^     (which is the position of the new node) 
      this column tells us 
      if we should proceed to the L or R child at each level 

EDIT: Thêm một mô tả trên làm thế nào để có được các nút mới trong số bước ngắn nhất giả định rằng chúng tôi biết tổng số các nút trong cây.

Answer 2

Về cơ bản, báo cáo được trích dẫn đề cập đến vấn đề giải quyết vị trí để chèn và xóa các phần tử dữ liệu vào và ra khỏi vùng heap. Để duy trì "thuộc tính hình dạng" của một đống nhị phân, mức thấp nhất của đống phải luôn được điền từ trái sang phải để lại không có nút trống nào. Để duy trì thời gian chèn và xóa trung bình O (1) cho vùng nhị phân, bạn phải có khả năng xác định vị trí chèn tiếp theo và vị trí của nút cuối cùng ở mức thấp nhất để sử dụng để xóa nút gốc, cả hai trong thời gian không đổi.

Đối với một heap nhị phân được lưu trữ trong một mảng (với cấu trúc dữ liệu được nén chặt chẽ như được giải thích trong mục nhập Wikipedia), điều này rất dễ dàng. Chỉ cần chèn thành viên dữ liệu mới nhất vào cuối mảng và sau đó "bong bóng" nó vào vị trí (theo các quy tắc heap). Hoặc thay thế gốc bằng phần tử cuối cùng trong mảng "sủi bọt xuống" để xóa. Đối với heaps trong mảng lưu trữ, số lượng các phần tử trong heap là một con trỏ ngầm đến nơi mà phần tử dữ liệu tiếp theo được chèn vào và nơi tìm phần tử cuối cùng để sử dụng để xóa.

Đối với một đống nhị phân được lưu trữ trong cấu trúc cây, thông tin này không rõ ràng, nhưng vì đó là một cây nhị phân hoàn chỉnh, nó có thể được tính toán. Ví dụ, trong một cây nhị phân hoàn chỉnh với 4 phần tử, điểm chèn sẽ luôn là con phải của con trái của nút gốc. Nút để sử dụng để xóa sẽ luôn là con trái của con trái của nút gốc. Và đối với bất kỳ kích thước cây tùy ý nào, cây sẽ luôn có một hình dạng cụ thể với các điểm chèn và xóa được xác định rõ. Bởi vì cây là một "cây nhị phân hoàn chỉnh" với một cấu trúc cụ thể cho bất kỳ kích thước nhất định nào, rất có thể tính toán vị trí chèn/xóa trong thời gian O (1). Tuy nhiên, việc nắm bắt được rằng ngay cả khi bạn biết nó ở đâu về mặt cấu trúc, bạn không có ý tưởng về nơi nút sẽ nằm trong bộ nhớ. Vì vậy, bạn phải đi qua cây để đến nút đã cho, đó là một quá trình O (log n) làm cho tất cả chèn và xóa tối thiểu O (log n), phá vỡ hành vi O (1) thường mong muốn. Bất kỳ tìm kiếm ("chiều sâu đầu tiên", hoặc một số khác) sẽ có ít nhất O (log n) cũng vì vấn đề traversal lưu ý và thường O (n) vì bản chất ngẫu nhiên của đống bán được sắp xếp.

Bí quyết là để có thể cả tính và tham khảo những chèn/điểm xóa trong thời gian liên tục bằng cách làm tăng cấu trúc dữ liệu ("luồng" cây, như đề cập trong bài viết Wikipedia) hoặc sử dụng thêm con trỏ. Việc thực hiện dường như tôi dễ hiểu nhất, với bộ nhớ thấp và chi phí mã hóa cao hơn, là chỉ cần sử dụng cấu trúc cây nhị phân đơn giản bình thường (sử dụng một pRoot và Node được định nghĩa là [data, pParent, pLeftChild, pRightChild]) và thêm hai con trỏ bổ sung (pInsert và pLastNode). pInsert và pLastNode cả hai sẽ được cập nhật trong quá trình chèn và xóa các chương trình con để giữ chúng hiện tại khi dữ liệu trong cấu trúc thay đổi. Việc thực hiện này cho phép O (1) truy cập vào cả hai điểm chèn và nút cuối cùng của cấu trúc và nên cho phép bảo toàn toàn bộ hành vi O (1) trong cả việc chèn và xóa. Chi phí thực hiện là hai con trỏ bổ sung và một số mã phụ nhỏ trong các chương trình con chèn/xóa (aka, minimal).

EDIT: thêm mã giả cho một O (1) chèn()

Đây là mã giả cho một chương trình con chèn là O (1), trung bình:

define Node = [T data, *pParent, *pLeft, *pRight] 

void insert(T data) 
{ 
    do_insertion(data); // do insertion, update count of data items in tree 

    # assume: pInsert points node location of the tree that where insertion just took place 
    # (aka, either shuffle only data during the insertion or keep pInsert updated during the bubble process) 

    int N = this->CountOfDataItems + 1;  # note: CountOfDataItems will always be > 0 (and pRoot != null) after an insertion 

    p = new Node(<null>, null, null, null);  // new empty node for the next insertion 

    # update pInsert (three cases to handle) 
    if (int(log2(N)) == log2(N)) 
     {# #1 - N is an exact power of two 
     # O(log2(N)) 
     # tree is currently a full complete binary tree ("perfect") 
     # ... must start a new lower level 
     # traverse from pRoot down tree thru each pLeft until empty pLeft is found for insertion 
     pInsert = pRoot; 
     while (pInsert->pLeft != null) { pInsert = pInsert->pLeft; } # log2(N) iterations 
     p->pParent = pInsert; 
     pInsert->pLeft = p; 
     } 
    else if (isEven(N)) 
     {# #2 - N is even (and NOT a power of 2) 
     # O(1) 
     p->pParent = pInsert->pParent; 
     pInsert->pParent->pRight = p; 
     } 
    else 
     {# #3 - N is odd 
     # O(1) 
     p->pParent = pInsert->pParent->pParent->pRight; 
     pInsert->pParent->pParent->pRight->pLeft = p; 
     } 
    pInsert = p; 

    // update pLastNode 
    // ... [similar process] 
} 

Vì vậy, chèn (T) là O (1) trên trung bình: chính xác O (1) trong mọi trường hợp ngoại trừ khi cây phải được tăng lên một cấp khi nó là O (log N), xảy ra mỗi lần đăng nhập N (giả sử không có xóa) . Việc thêm một con trỏ khác (pLeftmostLeaf) có thể làm cho insert() O (1) cho tất cả các trường hợp và tránh trường hợp bệnh lý có thể chèn xen kẽ xen kẽ & xóa toàn bộ một cây nhị phân đầy đủ. (Thêm pLeftmost là trái như là một bài tập [nó khá dễ dàng].)

Answer 3

Giải pháp trong trường hợp bạn không có tham chiếu đến cha mẹ !!! Để tìm đúng nơi cho nút kế tiếp, bạn có 3 trường hợp để xử lý

• trường hợp (1) mức Tree hoàn tất log2 (N)
• trường hợp (2) đếm nút Tree thậm chí còn
• trường hợp (3) đếm nút Tree là lẻ

Insert:

void Insert(Node root,Node n) 
{ 
Node parent = findRequiredParentToInsertNewNode (root); 
if(parent.left == null) 
parent.left = n; 
else 
parent.right = n; 
} 

Tìm phụ huynh của nút để chèn nó

void findRequiredParentToInsertNewNode(Node root){ 

Node last = findLastNode(root); 

//Case 1 
if(2*Math.Pow(levelNumber) == NodeCount){ 
    while(root.left != null) 
     root=root.left; 
    return root; 
} 
//Case 2 
else if(Even(N)){ 
    Node n =findParentOfLastNode(root ,findParentOfLastNode(root ,last)); 
return n.right; 
} 
//Case 3 
else if(Odd(N)){ 
    Node n =findParentOfLastNode(root ,last); 
return n; 
} 

} 

Để tìm nút cuối cùng bạn cần phải thực hiện một BFS (theo chiều rộng tìm kiếm đầu tiên) và nhận được yếu tố cuối cùng trong hàng đợi

Node findLastNode(Node root) 
{ 
    if (root.left == nil) 
     return root 

    Queue q = new Queue(); 

    q.enqueue(root); 
    Node n = null; 

    while(!q.isEmpty()){ 
     n = q.dequeue(); 
    if (n.left != null) 
     q.enqueue(n.left); 
    if (n.right != null) 
     q.enqueue(n.right); 
     } 
    return n; 
} 

Tìm phụ huynh của nút cuối cùng để thiết lập nút null trong trường hợp thay thế với gốc trong trường hợp loại bỏ

Node findParentOfLastNode(Node root ,Node lastNode) 
{ 
    if(root == null) 
     return root; 

    if(root.left == lastNode || root.right == lastNode) 
     return root; 

    Node n1= findParentOfLastNode(root.left,lastNode); 
    Node n2= findParentOfLastNode(root.left,lastNode); 

    return n1 != null ? n1 : n2; 
} 

Answer 4

Bạn có thể sử dụng các biểu diễn nhị phân của kích thước của binary Heap để tìm vị trí của nút cuối cùng trong thời gian O (log N). Kích thước có thể được lưu trữ và tăng lên mà sẽ mất O (1) thời gian. Khái niệm cơ bản đằng sau này là cấu trúc của cây nhị phân.

Giả sử kích thước heap của chúng tôi là 7. Biểu diễn nhị phân của 7 là "111".Bây giờ, hãy nhớ luôn bỏ qua bit đầu tiên. Vì vậy, bây giờ chúng tôi còn lại với "11". Đọc từ trái sang phải. Bit này là '1', vì vậy, hãy chuyển đến nút con bên phải của nút gốc. Sau đó, chuỗi còn lại là "1", bit đầu tiên là '1'. Vì vậy, một lần nữa đi đến con phải của nút hiện tại bạn đang ở. Vì bạn không còn có bit để xử lý, điều này chỉ ra rằng bạn đã đạt đến nút cuối cùng. Vì vậy, quá trình làm việc thô của quá trình này là, chuyển đổi kích thước của heap thành bit. Bỏ qua bit đầu tiên. Theo bit ngoài cùng bên trái, hãy chuyển đến nút con bên phải của nút hiện tại nếu nó là '1', và sang bên trái của nút hiện tại nếu nó là '0'.

Khi bạn luôn luôn đến tận cùng của cây nhị phân, thao tác này luôn mất thời gian O (log N). Đây là một thủ tục đơn giản và chính xác để tìm nút cuối cùng.

Bạn có thể không hiểu nó trong lần đọc đầu tiên. Hãy thử làm việc phương pháp này trên giấy cho các giá trị khác nhau của nhị phân Heap, tôi chắc chắn bạn sẽ nhận được trực giác đằng sau nó. Tôi chắc chắn rằng kiến ​​thức này là đủ để giải quyết vấn đề của bạn, nếu bạn muốn giải thích thêm với các số liệu, bạn có thể tham khảo blog của tôi.

Hy vọng câu trả lời của tôi đã giúp bạn, nếu có, hãy cho tôi biết ...! ☺

Answer 5

Lần đầu tiên tôi tham gia tràn ngăn xếp.

Có, câu trả lời ở trên bởi Zach Scrivena (thần tôi không biết cách tham khảo đúng cách với người khác, xin lỗi) là đúng. Những gì tôi muốn thêm là một cách đơn giản nếu chúng tôi được cung cấp số lượng nút.

Ý tưởng cơ bản là:

Với đếm N nút trong cây nhị phân đầy đủ này, làm "N% 2" tính toán và đẩy các kết quả vào một chồng. Tiếp tục tính toán cho đến khi N == 1. Sau đó bật kết quả ra. Kết quả là 1 có nghĩa là đúng, 0 có nghĩa là trái. Trình tự là tuyến từ gốc đến vị trí đích.

Ví dụ:

Cây bây giờ có 10 nút, tôi muốn chèn một nút khác ở vị trí 11. Làm thế nào để định tuyến nó?

11 % 2 = 1 --> right (the quotient is 5, and push right into stack) 
5 % 2 = 1 --> right (the quotient is 2, and push right into stack) 
2 % 2 = 0 --> left  (the quotient is 1, and push left into stack. End) 

Sau đó bật ngăn xếp: trái -> phải -> phải. Đây là con đường từ gốc.

Answer 6

Tôi biết đây là một chủ đề cũ nhưng tôi đang tìm kiếm câu trả lời cho cùng một câu hỏi. Nhưng tôi không thể đủ khả năng để làm một o (log n) giải pháp như tôi đã phải tìm nút cuối cùng hàng ngàn lần trong một vài giây. Tôi đã có một thuật toán O (log n) nhưng chương trình của tôi đã thu thập dữ liệu vì số lần nó thực hiện thao tác này. Vì vậy, sau nhiều suy nghĩ tôi cuối cùng đã tìm thấy một sửa chữa cho việc này. Không chắc chắn nếu bất cứ ai điều này là thú vị.

Giải pháp này là O (1) để tìm kiếm. Để chèn nó chắc chắn là ít hơn O (log n), mặc dù tôi không thể nói nó là O (1).

Chỉ muốn thêm rằng nếu có sự quan tâm, tôi cũng có thể cung cấp giải pháp của mình. Giải pháp là thêm các nút trong vùng nhị phân vào hàng đợi. Mỗi nút hàng đợi có con trỏ phía trước và phía sau.Chúng tôi tiếp tục thêm các nút vào cuối hàng đợi này từ trái sang phải cho đến khi chúng tôi đến nút cuối cùng trong vùng nhị phân. Tại thời điểm này, nút cuối cùng trong đống nhị phân sẽ nằm ở phía sau hàng đợi. Mỗi lần chúng ta cần phải tìm nút cuối cùng, chúng ta dequeue từ phía sau, và thứ hai-to-last bây giờ trở thành nút cuối cùng trong cây. Khi chúng tôi muốn chèn, chúng tôi tìm kiếm ngược từ phía sau cho nút đầu tiên, nơi chúng tôi có thể chèn và đặt nó ở đó. Nó không phải là chính xác O (1) nhưng làm giảm đáng kể thời gian chạy.