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




b+ tree (4)

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

उदाहरण के लिए, आदेश के बी-पेड़ पर विचार करें 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

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

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


निम्नलिखित चाल को सबसे अधिक आदेशित खोज पेड़ों के लिए काम करना चाहिए, मानते हुए डेटा को पूर्णांक 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

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

[ संपादित करें मैंने अभी महसूस किया है कि उस क्रम में कुंजी तक पहुंचने के लिए आपको उन बिट-रिवर्स किए गए मानों के आधार पर डेटा को सॉर्ट करने की आवश्यकता नहीं है। उस पर चाल यह ध्यान देने योग्य है कि बिट-रिवर्सिंग स्वयं का उलटा है। साथ ही पदों के लिए मैपिंग कुंजी, यह कुंजी को पदों पर नक्शा बनाता है। तो यदि आप 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

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


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

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

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

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

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

नोट संपादित करें : चूंकि सवाल काफी रोचक था, इसलिए मैं थोड़ा सा हास्केल के साथ अपना जवाब सुधारने की कोशिश करता हूं।

चलो बी-ट्री के Knuth आदेश हो और कुंजी की एक सूची सूचीबद्ध करें

अंतरिक्ष खपत को कम करने के लिए एक मामूली समाधान है:

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

इस तरह के एल्गोरिदम कुशलता से समय-अक्षम बी-ट्री का उत्पादन करेंगे, बाएं असंतुलित लेकिन कम से कम अंतरिक्ष खपत के साथ।

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

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

-- 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, 5, 9, 1, 2, 6, 7, 12, 16, 21] जिसके परिणामस्वरूप बी-पेड़ की तरह

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

स्पष्ट रूप से यह एक प्रदर्शन बिंदु से उप-विशिष्ट है, लेकिन स्वीकार्य होना चाहिए, क्योंकि एक बेहतर प्राप्त करना (निम्न की तरह) कहीं अधिक महंगा होगा (कम्प्यूटेशनल और आर्थिक रूप से):

          [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

एक ब्लैक बॉक्स के रूप में सम्मिलित करें () का उपयोग करके एक विशेष बी-पेड़ बनाने के लिए, पिछड़ा काम करें। एक 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

एट कैटेरा





b-tree