न्यूनतम ऊंचाई प्राप्त करने के लिए आपको बी-ट्री में ज्ञात कुंजियों का एक सेट किस क्रम में डालना चाहिए?

Question

एक निश्चित संख्या में कुंजी या मान (सरणी में या कुछ डेटा संरचना में संग्रहीत) और बी-पेड़ के क्रम को देखते हुए, क्या हम एक डालने वाली कुंजी के अनुक्रम को निर्धारित कर सकते हैं जो अंतरिक्ष कुशल बी-पेड़ उत्पन्न करेगा।

उदाहरण के लिए, ऑर्डर के बी-पेड़ पर विचार करें 3. चाबियां {1,2,3,4,5,6,7} बनें। नीचे दिए गए क्रम

for(int i=1 ;i<8; ++i) 
{ 
tree.push(i); 
} 

में पेड़ में तत्वों को सम्मिलित की तरह इस

 4 
    2  6 
    1 3 5 7 

देख http://en.wikipedia.org/wiki/B-tree

लेकिन इस तरह से

flag = true; 
for(int i=1,j=7; i<8; ++i,--j) 
{ 
    if(flag) 
    { 
     tree.push(i); 
     flag = false; 
    } 
    else 
    { 
     tree.push(j); 
     flag = true; 
    } 
} 

में तत्वों डालने एक पेड़ बनाता है एक पेड़ बन जाएगा इस तरह

3 5 
1 2 4 6 7 

जहां हम देख सकते हैं कि स्तर में कमी आई है।

तो क्या सम्मिलन के अनुक्रम को निर्धारित करने का एक विशेष तरीका है जो अंतरिक्ष की खपत को कम करेगा?

Answer 1

दुर्भाग्यवश, सभी पेड़ अपने सबसे बुरे केस परिदृश्य को चलने वाले समय प्रदर्शित करते हैं, और जब इस तरह के क्रम में डेटा दर्ज किया जाता है तो कठोर संतुलन तकनीक की आवश्यकता होती है। बाइनरी पेड़ जल्दी से लिंक्ड सूचियों में बदल जाते हैं, आदि

ठेठ बी-ट्री उपयोग के मामलों (डेटाबेस, फाइल सिस्टम, आदि) के लिए, आप आम तौर पर अपने दूसरे उदाहरण की तरह पेड़ का उत्पादन करने के लिए स्वाभाविक रूप से अधिक वितरित होने वाले डेटा पर भरोसा कर सकते हैं।

हालांकि यह वास्तव में एक चिंता है, तो आप मूल्यों के व्यापक वितरण की गारंटी देते हुए प्रत्येक कुंजी को हश कर सकते हैं।

for(i=1; i<8; ++i) 
    tree.push(hash(i)); 

Answer 2

निम्नलिखित चाल सबसे आदेश दिया खोज पेड़ों के लिए काम करना चाहिए, पूर्णांकों 1..n हैं सम्मिलित करने के लिए डेटा संभालने। कम से कम अक्सर 1..7 के लिए (शून्य के लिए डॉट्स के साथ) है कि ...

Bit : 210 
    1 : ..1 
    2 : .1. 
    3 : .11 
    4 : 1.. 
    5 : 1.1 
    6 : 11. 
    7 : 111 

बिट 2 परिवर्तन, बिट 0 परिवर्तन सबसे अधिक बार -

द्विआधारी अपने पूर्णांक चाबियों का प्रतिनिधित्व पर विचार करें। यही कारण है कि हम क्या चाहते हैं, तो क्या होगा अगर हम उन बिट्स के क्रम को उल्टा, तो हमारे चाबियाँ इस बिट उलट मूल्य के क्रम में सॉर्ट के विपरीत है ...

Bit : 210 Rev 
    4 : 1.. -> ..1 : 1 
    ------------------ 
    2 : .1. -> .1. : 2 
    6 : 11. -> .11 : 3 
    ------------------ 
    1 : ..1 -> 1.. : 4 
    5 : 1.1 -> 1.1 : 5 
    3 : .11 -> 11. : 6 
    7 : 111 -> 111 : 7 

यह एक के मामले में यह समझाने के लिए सबसे आसान है असंतुलित बाइनरी खोज पेड़, पत्तियों को जोड़कर बढ़ रहा है। पहला आइटम मृत केंद्र है - यह वही वस्तु है जिसे हम रूट के लिए चाहते हैं। फिर हम अगली परत के लिए कुंजी जोड़ते हैं। अंत में, हम पत्ती परत जोड़ते हैं। हर कदम पर, पेड़ उतना ही संतुलित होता है जितना हो सकता है, इसलिए यदि आप एवीएल या लाल-काले संतुलित पेड़ का निर्माण करते हैं, तो पुनर्विक्रेता तर्क कभी भी नहीं बुलाया जाना चाहिए।

[EDIT मुझे अभी एहसास हुआ कि आपको उस क्रम में कुंजी तक पहुंचने के लिए उन बिट-रिवर्स किए गए मानों के आधार पर डेटा को सॉर्ट करने की आवश्यकता नहीं है। उस पर चाल यह ध्यान देने योग्य है कि बिट-रिवर्सिंग स्वयं का उलटा है। साथ ही पदों के लिए मैपिंग कुंजी, यह कुंजी को पदों पर नक्शा बनाता है। तो अगर आप 1 से लूप ..n, आप इस बिट-रिवर्स किए गए मान का उपयोग यह तय करने के लिए कर सकते हैं कि कौन सी वस्तु अगले डालने के लिए है - पहले डालने के लिए चौथी वस्तु का उपयोग करें, दूसरे डालने के लिए दूसरी वस्तु का उपयोग करें और इसी तरह। एक जटिलता - आपको दो की शक्ति से एक से ऊपर की तरफ बढ़ना होगा (7 ठीक है, लेकिन 8 के बजाय 15 का उपयोग करें) और आपको बिट-रिवर्स किए गए मानों को बाध्य करना होगा। कारण यह है कि थोड़ा-पीछे बाहर के सीमा और वीजा प्रतिकूल कुछ में-सीमा पदों स्थानांतरित कर सकते हैं।]

वास्तव में, एक लाल-काले पेड़ के लिए कुछ पुनर्संतुलन तर्क लागू हो जाएगा, लेकिन यह सिर्फ होना चाहिए फिर से रंग नोड्स - उन्हें पुनर्व्यवस्थित नहीं। हालांकि, मैंने दो बार चेक नहीं किया है, इसलिए इस दावे पर भरोसा न करें।

एक बी पेड़ के लिए, पेड़ की ऊंचाई एक नया रूट जोड़कर बढ़ता है। इसलिए, यह काम प्रदान करना थोड़ा अजीब है (और इसे सामान्य रूप से आवश्यक एक बी पेड़ की तुलना में अधिक सावधानीपूर्वक नोड-विभाजन की आवश्यकता हो सकती है) लेकिन मूल विचार समान है। हालांकि पुनर्वितरण होता है, यह आवेषण के आदेश के कारण संतुलित तरीके से होता है।

यह जाना जाता है में अग्रिम कुंजी के किसी सेट के लिए सामान्यीकृत किया जा सकता, क्योंकि एक बार कुंजी हल कर रहे हैं, तो आप उस क्रमबद्ध आदेश के आधार पर उपयुक्त अनुक्रमित असाइन कर सकते हैं।

---

चेतावनी - यह जाना जाता है पहले से ही हल कर डेटा से एक अच्छी तरह से संतुलित पेड़ के निर्माण के लिए एक कारगर तरीका नहीं है।

आप अपने डेटा पहले से ही क्रमित है, और पता है कि यह आकार है, तो आप हे (एन) के समय में एक अच्छी तरह से संतुलित पेड़ बना सकते हैं। यहाँ कुछ स्यूडोकोड है ...

if size is zero, return null 
from the size, decide which index should be the (subtree) root 
recurse for the left subtree, giving that index as the size (assuming 0 is a valid index) 
take the next item to build the (subtree) root 
recurse for the right subtree, giving (size - (index + 1)) as the size 
add the left and right subtree results as the child pointers 
return the new (subtree) root 

असल में, इस पेड़ के आकार के आधार की संरचना का फैसला करता है और उस संरचना को पार करता, रास्ते में वास्तविक नोड्स के निर्माण। बी पेड़ के लिए इसे अनुकूलित करना बहुत कठिन नहीं होना चाहिए।

Answer 3

एक विशेष बी पेड़ एक ब्लैक बॉक्स के रूप में सम्मिलित करें() का उपयोग कर निर्माण करने के लिए, पिछड़े काम करते हैं। एक nonempty बी-पेड़ को देखते हुए, संभवतः पत्तियों के करीब जितना संभव हो उतने बच्चों की तुलना में एक नोड पाएं। रूट को न्यूनतम 0 माना जाता है, इसलिए न्यूनतम संख्या में बच्चों के साथ एक नोड हमेशा मौजूद होता है। सम्मिलित करें() कॉल की सूची में प्रीपेड होने के लिए इस नोड से एक मान हटाएं। पत्तियों की ओर काम करते हैं, subtrees विलय।

उदाहरण के लिए, 2-3 पेड़

 8 
    4  c 
2 6 a e 
1 3 5 7 9 b d f, 

हम 8 चुनते हैं और कर दिया पूर्ववर्ती

4  c 
2 6 a e 
1 3 5 79 b d f. 

फिर हम 9.

4  c 
2 6 a e 
1 3 5 7 b d f 

तब चुनें प्राप्त करने के लिए विलीन हो जाती है ए।

4 c 
2 6 e 
1 3 5 7b d f 

फिर बी।

4 c 
2 6 e 
1 3 5 7 d f 

फिर सी।

4 
2 6 e 
1 3 5 7d f 

एट कैटेरा।

Answer 4

यह कैसे मैं बी पेड़ से तत्वों को जोड़ने होता है।

Steve314 के लिए धन्यवाद, मुझे,

को देखते हुए द्विआधारी प्रतिनिधित्व के साथ शुरू देने के लिए एन के क्रम में, जोड़ने के लिए तत्व हैं। हमें इसे एम-ऑर्डर बी-पेड़ में जोड़ना है। अपनी अनुक्रमणिका लें (1 ... एन) और इसे रेडिक्स एम में परिवर्तित करें। इस सम्मिलन का मुख्य विचार वर्तमान में उच्चतम एम-रेडिक्स बिट के साथ संख्या डालना है और नोड्स के विभाजन के बावजूद पेड़ में जोड़े गए कम एम-रेडिक्स संख्याओं से ऊपर रखना है।

1,2,3 .. इंडेक्स हैं इसलिए आप वास्तव में उन संख्याओं को सम्मिलित करते हैं जिन्हें वे इंगित करते हैं।

For example, order-4 tree 
     4  8   12   highest radix bit numbers 
1,2,3 5,6,7 9,10,11 13,14,15 

अब आदेश मंझला के आधार पर किया जा सकता है:

• आदेश भी है -> कुंजियों की संख्या करीब हैं -> मंझला बीच (मध्य मंझला) है
• क्रम अजीब है -> की संख्या चाबियां भी हैं -> बाएं औसत या दाएं औसत

पदोन्नति के लिए औसत (बाएं/दाएं) की पसंद का निर्णय तय करेगा जिसमें मुझे तत्व डालना चाहिए। यह बी-पेड़ के लिए तय किया जाना है।

मैं बाल्टी में पेड़ के तत्व जोड़ता हूं। सबसे पहले मैं अगली बाल्टी को पूरा करने पर बाल्टी तत्व जोड़ता हूं। यदि मध्यस्थ जाना जाता है तो बाल्टी आसानी से बनाई जा सकती है, बाल्टी का आकार ऑर्डर मी है।

I take left median for promotion. Choosing bucket for insertion. 
    | 4  | 8  | 12  |  
1,2,|3 5,6,|7 9,10,|11 13,14,|15 
     3  2   1    Order to insert buckets. 

• बाएं मंझला चुनाव के लिए मैं दाईं ओर से शुरू, मैं बाईं ओर से बाल्टी डालने सही मंझला चुनाव के लिए पेड़ से बाल्टी डालें। बाएं-मध्यस्थ का चयन करना हम पहले मध्यस्थ को सम्मिलित करते हैं, फिर तत्वों को छोड़कर पहले बाल्टी में शेष संख्याएं।

उदाहरण

Bucket median first 
12, 
Add elements to left 
11,12, 
Then after all elements inserted it looks like, 
| 12  | 
|11 13,14,| 
Then I choose the bucket left to it. And repeat the same process. 
Median 
    12   
8,11 13,14, 
Add elements to left first 
     12   
7,8,11 13,14, 
Adding rest 
    8  | 12   
7 9,10,|11 13,14, 
Similarly keep adding all the numbers, 
    4  | 8  | 12   
3 5,6,|7 9,10,|11 13,14, 
At the end add numbers left out from buckets. 
    | 4  | 8  | 12  | 
1,2,|3 5,6,|7 9,10,|11 13,14,|15 

• मध्य मंझला (यहां तक ​​कि आदेश बी-वृक्ष) आप बस मंझला बाल्टी में सभी नंबरों को सम्मिलित करने और उसके बाद के लिए।

• दाएं-मध्य के लिए मैं बाएं से बाल्टी जोड़ता हूं। बाल्टी के भीतर तत्वों के लिए मैं पहले मध्यस्थ को सही तत्वों और फिर तत्वों को छोड़ देता हूं।

यहाँ हम उच्चतम एम-मूलांक संख्या जोड़ रहे हैं, और इस प्रक्रिया में मैं तत्काल कम एम-मूलांक बिट के साथ नंबर जोड़ा है, यकीन है कि उच्चतम एम-मूलांक संख्या शीर्ष पर रहने के लिए बना। यहां मेरे पास केवल दो स्तर हैं, अधिक स्तरों के लिए मैं रेडिक्स बिट्स के अवरोही क्रम में एक ही प्रक्रिया को दोहराता हूं।

अंतिम मामला तो बस उन्हें डाल सकते हैं और प्रक्रिया समाप्त है, जब शेष तत्व एक ही मूलांक-बिट के हैं और वहाँ कम मूलांक-बिट के साथ कोई संख्या है।

मैं 3 स्तरों के लिए एक उदाहरण देना होगा, लेकिन यह भी दिखाने के लिए लंबा है। तो अन्य मानकों के साथ कोशिश करते हैं और बताती हैं कि यह काम करता है कृपया।

Answer 5

तो वहाँ प्रविष्टि के अनुक्रम जो स्थान खपत को कम करेगा निर्धारित करने के लिए एक विशेष तरीका है?

संपादित करें टिप्पणी: के बाद से सवाल काफी रोचक था, मैं हास्केल का एक सा के साथ मेरा उत्तर सुधार करने के लिए प्रयास करें।

-- won't use point free notation to ease haskell newbies 
trivial k list = concat $ reverse $ chunksOf (k-1) $ sort list 

इस तरह के एल्गोरिथ्म कुशलतापूर्वक एक का उत्पादन करेगा:

Let बी ट्री और list कुंजी

स्थान खपत को न्यूनतम एक छोटी सी समाधान है की एक सूची के नुथ आदेश हो kसमय-अक्षम बी-ट्री, बाईं ओर असंतुलित लेकिन न्यूनतम स्पेस खपत के साथ।

बहुत सारे गैर-छोटे समाधान मौजूद हैं जो उत्पादन के लिए कम कुशल हैं लेकिन बेहतर लुकअप प्रदर्शन (निचली ऊंचाई/गहराई) दिखाते हैं। जैसा कि आप जानते हैं, यह व्यापार-बंद के बारे में है!

एक साधारण एल्गोरिथ्म है कि दोनों बी ट्री गहराई और अंतरिक्ष की खपत को कम करता है (लेकिन यह देखने प्रदर्शन को कम नहीं करता है!), निम्नलिखित

-- Sort the list in increasing order and call sortByBTreeSpaceConsumption 
-- with the result 
smart k list = sortByBTreeSpaceConsumption k $ sort list 

-- Sort list so that inserting in a B-Tree with Knuth order = k 
-- will produce a B-Tree with minimal space consumption minimal depth 
-- (but not best performance) 
sortByBTreeSpaceConsumption :: Ord a => Int -> [a] -> [a] 
sortByBTreeSpaceConsumption _ [] = [] 
sortByBTreeSpaceConsumption k list 
    | k - 1 >= numOfItems = list -- this will be a leaf 
    | otherwise = heads ++ tails ++ sortByBTreeSpaceConsumption k remainder 
    where requiredLayers = minNumberOfLayersToArrange k list 
      numOfItems = length list 
      capacityOfInnerLayers = capacityOfBTree k $ requiredLayers - 1 
      blockSize = capacityOfInnerLayers + 1 
      blocks = chunksOf blockSize balanced 
      heads = map last blocks 
      tails = concat $ map (sortByBTreeSpaceConsumption k . init) blocks 
      balanced = take (numOfItems - (mod numOfItems blockSize)) list 
      remainder = drop (numOfItems - (mod numOfItems blockSize)) list 

-- Capacity of a layer n in a B-Tree with Knuth order = k 
layerCapacity k 0 = k - 1 
layerCapacity k n = k * layerCapacity k (n - 1) 

-- Infinite list of capacities of layers in a B-Tree with Knuth order = k 
capacitiesOfLayers k = map (layerCapacity k) [0..] 

-- Capacity of a B-Tree with Knut order = k and l layers 
capacityOfBTree k l = sum $ take l $ capacitiesOfLayers k 

-- Infinite list of capacities of B-Trees with Knuth order = k 
-- as the number of layers increases 
capacitiesOfBTree k = map (capacityOfBTree k) [1..] 

-- compute the minimum number of layers in a B-Tree of Knuth order k 
-- required to store the items in list 
minNumberOfLayersToArrange k list = 1 + f k 
    where numOfItems = length list 
      f = length . takeWhile (< numOfItems) . capacitiesOfBTree 

इस smart समारोह के साथ

है एक list = [21, 18, 16, 9, 12, 7, 6, 5, 1, 2] दिया और नुथ क्रम = 3 हम

   [18, 21] 
      /
     [5 , 9] 
    / | \ 
[1,2] [6,7] [12, 16] 

की तरह एक परिणामस्वरूप बी ट्री के साथ [18, 5, 9, 1, 2, 6, 7, 12, 16, 21] प्राप्त करना चाहिए के साथ एक बी-ट्री जाहिर है यह एक प्रदर्शन अंक से करने से इनकी है देखने के टी, लेकिन स्वीकार्य होना चाहिए, एक बेहतर एक प्राप्त करने के बाद से (जैसे निम्नलिखित) (computationally और आर्थिक रूप से) कहीं अधिक महंगा होगा:

  [7 , 16] 
     / | \ 
    [5,6] [9,12] [18, 21] 
    /
[1,2] 

आप इसे चलाने के लिए चाहते हैं, एक में पिछले कोड संकलन Main.hs फ़ाइल और यह संकलन GHC साथ

import Data.List (sort) 
import Data.List.Split 
import System.Environment (getArgs) 

main = do 
    args <- getArgs 
    let knuthOrder = read $ head args 
    let keys = (map read $ tail args) :: [Int] 
    putStr "smart: " 
    putStrLn $ show $ smart knuthOrder keys 
    putStr "trivial: " 
    putStrLn $ show $ trivial knuthOrder keys