लाल-काले पेड़ 2-3-4 पेड़ों के लिए आइसोमोर्फिक कैसे हैं?

Question

मुझे लाल काले पेड़ और 2-3-4 पेड़ दोनों की बुनियादी समझ है और यह सुनिश्चित करने के लिए कि वे सबसे खराब केस ऑपरेशंस ओ (एन लॉगन) हैं, वे ऊंचाई संतुलन कैसे बनाए रखते हैं।

लेकिन, मुझे लाल-काले पेड़ों की एक isometry रहे Wikipedia

2-3-4 पेड़ से इस पाठ को समझने में सक्षम नहीं हूँ, जिसका अर्थ है कि वे बराबर डेटा संरचनाओं हैं। दूसरे शब्दों में, प्रत्येक 2-3-4 पेड़ के लिए, कम से कम एक लाल-काले पेड़ मौजूद होता है जिसमें उसी क्रम में डेटा तत्व होते हैं। इसके अलावा, नोड विस्तार, विभाजन और विलय के कारण 2-3-4 पेड़ों पर सम्मिलन और विलोपन संचालन लाल-काले पेड़ों में रंग-फ़्लिपिंग और घूर्णन के बराबर होते हैं।

मुझे नहीं लगता कि संचालन बराबर कैसे हैं। विकिपीडिया पर यह उद्धरण सटीक है? कोई कैसे देख सकता है कि संचालन बराबर हैं?

Answer 1

आरबी-पेड़ (लाल-काला-पेड़) 2-3-4-पेड़ के लिए isomorphic नहीं है। क्योंकि अगर हम इस 3-नोड को आरबी-पेड़ में मैप करने का प्रयास करते हैं तो 2-3-4-पेड़ में 3-नोड दुबला या दायां हो सकता है। लेकिन llrb-tree (बाएं झुकाव लाल-काले पेड़) करता है। से Robert Sedgewick (Introduction खंड में)

शब्द:

In particular, the paper describes a way to maintain 
a correspondence between red-black trees and 2-3-4 trees, 
by interpreting red links as internal links in 3-nodes and 
4-nodes. Since red links can lean either way in 3-nodes 
(and, for some implementations in 4-nodes), the correspondence is not necessarily 1-1 

इसके अलावा Page29 और रॉबर्ट सेजविक से presentation की Page30। यह एलएलआरबी पेड़ के बारे में एक प्रस्तुति है।

और wikipedia में "रेड-ब्लैक ट्री" के "ऑर्डर 4 के बी-पेड़ के एनालॉजी" में यह एक अच्छा ग्राफ है।