Menu Close

Elemento del árbol binario completo según su posición

Un árbol binario completo es un árbol binario que tiene todos los nodos posibles hasta el penúltimo nivel, y donde los elementos del último nivel están colocados de izquierda a derecha sin dejar huecos entre ellos.

La numeración de los árboles binarios completos se realiza a partir de la raíz, recorriendo los niveles de izquierda a derecha. Por ejemplo,

                  1
                 /  \
                /    \
               /      \
              2        3
             / \      / \
            4   5    6   7
           / \ 
          8   9

Los árboles binarios se puede representar mediante el siguiente tipo

   data Arbol = H
              | N Integer Arbol Arbol
     deriving (Show, Eq)

Cada posición de un elemento de un árbol es una lista de movimientos hacia la izquierda o hacia la derecha. Por ejemplo, la posición de 9 en al árbol anterior es [I,I,D].

Los tipos de los movimientos y de las posiciones se definen por

   data Movimiento = I | D deriving (Show, Eq)
   type Posicion   = [Movimiento]

Definir la función

   elementoEnPosicion :: Posicion -> Integer

tal que (elementoEnPosicion ms) es el elemento en la posición ms. Por ejemplo,

   elementoEnPosicion [D,I]    ==  6
   elementoEnPosicion [D,D]    ==  7
   elementoEnPosicion [I,I,D]  ==  9
   elementoEnPosicion []       ==  1

Soluciones

import Test.QuickCheck
 
data Arbol = H
           | N Integer Arbol Arbol
  deriving (Eq, Show)
 
data Movimiento = I | D deriving (Show, Eq)
 
type Posicion = [Movimiento]
 
-- 1ª solución
-- ===========
 
elementoEnPosicion :: Posicion -> Integer
elementoEnPosicion ms =
  aux ms (arbolBinarioCompleto (2^(1 + length ms)))
  where aux []     (N x _ _) = x
        aux (I:ms) (N _ i _) = aux ms i
        aux (D:ms) (N _ _ d) = aux ms d
 
-- (arbolBinarioCompleto n) es el árbol binario completo con n
-- nodos. Por ejemplo, 
--    λ> arbolBinarioCompleto 4
--    N 1 (N 2 (N 4 H H) H) (N 3 H H)
--    λ> pPrint (arbolBinarioCompleto 9)
--    N 1
--      (N 2
--         (N 4
--            (N 8 H H)
--            (N 9 H H))
--         (N 5 H H))
--      (N 3
--         (N 6 H H)
--         (N 7 H H))
arbolBinarioCompleto :: Integer -> Arbol
arbolBinarioCompleto n = aux 1
  where aux i | i <= n    = N i (aux (2*i)) (aux (2*i+1))
              | otherwise = H
 
-- 2ª solución
-- ===========
 
elementoEnPosicion2 :: Posicion -> Integer
elementoEnPosicion2 = aux . reverse
  where aux []     = 1
        aux (I:ms) = 2 * aux ms
        aux (D:ms) = 2 * aux ms + 1
 
-- Equivalencia
-- ============
 
-- La propiedad es
prop_elementoEnPosicion_equiv :: Positive Integer -> Bool
prop_elementoEnPosicion_equiv (Positive n) =
  elementoEnPosicion  ps == n &&
  elementoEnPosicion2 ps == n 
  where ps = posicionDeElemento n
 
-- tal que (posicionDeElemento n) es la posición del elemento n en el
-- árbol binario completo. Por ejemplo,
--    posicionDeElemento 6  ==  [D,I]
--    posicionDeElemento 7  ==  [D,D]
--    posicionDeElemento 9  ==  [I,I,D]
--    posicionDeElemento 1  ==  []
posicionDeElemento :: Integer -> Posicion
posicionDeElemento n =
  [f x | x <- tail (reverse (binario n))]
  where f 0 = I
        f 1 = D
 
-- (binario n) es la lista de los dígitos de la representación binaria
-- de n. Por ejemplo,
--    binario 11  ==  [1,1,0,1]
binario :: Integer -> [Integer]
binario n
  | n < 2     = [n]
  | otherwise = n `mod` 2 : binario (n `div` 2)
 
-- La comprobación es
--    λ> quickCheck prop_elementoEnPosicion_equiv
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
--    λ> length (show (elementoEnPosicion (replicate (3*10^5) D)))
--    90310
--    (1.96 secs, 11,518,771,016 bytes)
--    λ> length (show (elementoEnPosicion2 (replicate (3*10^5) D)))
--    90310
--    (14.32 secs, 11,508,181,176 bytes)

Pensamiento

Las más hondas palabras
del sabio nos enseñan
lo que el silbar del viento cuando sopla
o el sonar de las aguas cuando ruedan.

Antonio Machado

Medio

3 soluciones de “Elemento del árbol binario completo según su posición

  1. frahidzam
    elementoEnPosicion :: Posicion -> Integer
    elementoEnPosicion [] = 1
    elementoEnPosicion xs = 1 + aux2 (aux1 xs)
      where aux1 xs = zip (reverse xs) [1..]
            aux2 []         = 0
            aux2 ((D,a):xs) = 2^a + aux2 xs
            aux2 ((I,a):xs) = 2^(a-1) + aux2 xs
  2. luipromor
    elementoEnPosicion :: Posicion -> Integer
    elementoEnPosicion [] = 1
    elementoEnPosicion (x:xs)
      | x == I    = 2^length xs     + elementoEnPosicion xs
      | otherwise = 2^length (x:xs) + elementoEnPosicion xs
  3. javmarcha1
    elementoEnPosicion :: Posicion -> Integer
    elementoEnPosicion [] = 1
    elementoEnPosicion (x:xs)
      | x == I    = 2^(length (x:xs)) + desviacionI (x:xs)
      | otherwise = sum [2^n | n <- [0..length (x:xs)]] - desviacionD (x:xs)
     
    desviacionD :: Posicion  -> Integer
    desviacionD xs = sum [2^(length xs - p) | p <- posicion I xs]
     
    desviacionI :: Posicion  -> Integer
    desviacionI xs = sum [2^(length xs - p) | p <- posicion D xs]
     
    posicion :: Eq a => a -> [a] -> [Int]
    posicion x ys = [n | (n,y) <- zip [1..] ys, x == y]

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.