ਲਾਲ-ਕਾਲੀ ਲੜੀ ਜਾਣ ਪਛਾਣ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਹਾਰਡ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਕੋਡਨੇਸ਼ਨ ਫੇਸਬੁੱਕ ਗੂਗਲ ਉਬੇਰ
ਐਡਵਾਂਸਡ ਡਾਟਾ .ਾਂਚਾ ਬਾਈਨਰੀ ਖੋਜ ਲੜੀ ਬਾਈਨਰੀ ਟਰੀ ਡਾਟਾ ਢਾਂਚਾ ਟ੍ਰੀ

ਲਾਲ ਕਾਲੀ ਲੜੀ ਇੱਕ ਸਵੈ-ਸੰਤੁਲਨ ਬਾਈਨਰੀ ਰੁੱਖ ਹੈ. ਇਸ ਰੁੱਖ ਵਿਚ, ਹਰ ਨੋਡ ਜਾਂ ਤਾਂ ਲਾਲ ਨੋਡ ਜਾਂ ਇਕ ਕਾਲਾ ਨੋਡ ਹੁੰਦਾ ਹੈ. ਇਸ ਲਾਲ-ਕਾਲੇ ਦਰੱਖਤ ਦੀ ਜਾਣ-ਪਛਾਣ ਵਿਚ, ਅਸੀਂ ਇਸ ਦੀਆਂ ਸਾਰੀਆਂ ਮੁੱ basicਲੀਆਂ ਵਿਸ਼ੇਸ਼ਤਾਵਾਂ ਨੂੰ coverੱਕਣ ਦੀ ਕੋਸ਼ਿਸ਼ ਕਰਾਂਗੇ.

ਲਾਲ-ਕਾਲੇ ਦਰੱਖਤ ਦੇ ਗੁਣ

  1. ਹਰ ਨੋਡ ਲਾਲ ਜਾਂ ਕਾਲੇ ਵਜੋਂ ਦਰਸਾਇਆ ਜਾਂਦਾ ਹੈ.
  2. ਰੂਟ ਨੋਡ ਹਮੇਸ਼ਾਂ ਕਾਲਾ ਹੁੰਦਾ ਹੈ.
  3. ਲਾਲ ਨੋਡ ਦਾ ਲਾਲ ਮਾਪਾ ਜਾਂ ਲਾਲ ਬੱਚਾ ਨਹੀਂ ਹੋ ਸਕਦਾ (ਮਤਲਬ ਕਿ ਕੋਈ ਵੀ ਦੋ ਲਾਲ ਨੋਡ ਆਸ ਪਾਸ ਨਹੀਂ ਹਨ).
  4. ਕਿਸੇ ਵੀ ਨੋਡ ਤੋਂ ਇਸਦੇ ਐਨਆਈਐਲ ਸੰਤਾਨ ਤੱਕ ਜਾਣ ਵਾਲੇ ਹਰੇਕ ਮਾਰਗ ਵਿੱਚ ਬਰਾਬਰ ਗਿਣਤੀ ਵਿੱਚ ਕਾਲੇ ਨੋਡ ਹੋਣੇ ਚਾਹੀਦੇ ਹਨ.

ਲਾਲ ਅਤੇ ਕਾਲੇ ਦਰੱਖਤ ਦੀਆਂ ਜਾਇਜ਼ ਅਤੇ ਗਲਤ ਉਦਾਹਰਣਾਂ

ਲਾਲ-ਕਾਲੀ ਲੜੀ ਜਾਣ ਪਛਾਣ

ਲਾਲ-ਕਾਲੀ ਲੜੀ ਜਾਣ ਪਛਾਣ

ਟਾਈਮ ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਸਾਰੇ ਬੀ ਐਸ ਟੀ ਓਪਰੇਸ਼ਨਜ ਜਿਵੇਂ ਕਿ ਖੋਜ, ਸੰਮਿਲਨ, ਹਟਾਉਣਾ, ਆਦਿ ਓ (ਐਚ) ਸਮੇਂ ਵਿੱਚ ਕੀਤੇ ਜਾ ਸਕਦੇ ਹਨ, ਜਿੱਥੇ ਕਿ ਲਾਲ-ਕਾਲੇ ਦਰੱਖਤ ਦੀ ਉਚਾਈ ਹੈ, ਅਤੇ ਸੰਤੁਲਿਤ ਬੀਐਸਟੀ ਲਈ ਉਚਾਈ ਹਮੇਸ਼ਾਂ ਕ੍ਰਮ ਦੀ ਹੁੰਦੀ ਹੈ ਲਾਗ (ਐਨ) [n-> ਨੋਡਾਂ ਦੀ ਗਿਣਤੀ].

ਖੋਜ ਕਰਨਾ = ਓ (ਲੌਗ (ਐਨ))
ਸੰਮਿਲਿਤ = ਓ (ਲੌਗ (ਐਨ))
ਹਟਾਉਣ = ਓ (ਲੌਗ (ਐਨ))

ਲਾਲ-ਕਾਲੀ ਲੜੀ ਵਿੱਚ ਬਲੈਕ ਉਚਾਈ

ਲਾਲ-ਕਾਲੇ ਰੁੱਖ ਦੀ ਕਾਲੀ ਉਚਾਈ ਨੂੰ ਕਿਸੇ ਨੋਡ ਤੋਂ ਪੱਤੇ ਤੱਕ (ਜੋ ਕਿ ਐਨਆਈਐਲ ਹੈ) ਸਧਾਰਣ ਮਾਰਗ 'ਤੇ ਕਾਲੇ ਨੋਡਾਂ ਦੀ ਸੰਖਿਆ ਵਜੋਂ ਦਰਸਾਇਆ ਗਿਆ ਹੈ (ਤੁਸੀਂ ਦੋ ਵਾਰ ਇੱਕੋ ਨੋਡ ਨਹੀਂ ਜਾਂਦੇ). ਇਹ bh (x) ਦੁਆਰਾ ਦਰਸਾਇਆ ਗਿਆ ਹੈ.

ਲਾਲ-ਕਾਲੇ ਰੁੱਖ ਦੀ ਉਚਾਈ

ਉਲਟ AVL ਰੁੱਖ, ਉਚਾਈ ਸੰਤੁਲਨ ਇੰਨਾ ਸਖਤ ਨਹੀਂ ਹੈ, ਪਰ ਲਾਲ-ਕਾਲੇ ਰੁੱਖਾਂ ਵਿੱਚ, ਘੁੰਮਣ ਦੀ ਗਿਣਤੀ ਏਵੀਐਲ ਦੇ ਰੁੱਖਾਂ ਦੀ ਤੁਲਨਾ ਵਿੱਚ ਘੱਟ ਹੈ.
ਲਾਲ-ਕਾਲੇ ਰੁੱਖ ਦੀ ਉਚਾਈ h <= 2 (ਲੌਗ (ਐਨ + 1)) log ਲੌਗ ਦਾ ਅਧਾਰ 2} ਵੇਰਵਾ ਹੈ ਸਬੂਤ ਆਰ ਬੀ ਦੇ ਦਰੱਖਤਾਂ ਦੀ ਉਚਾਈ ਕਿਉਂ ਹੈ <= 2 ਲੌਗ (ਐਨ + 1).

ਉਚਾਈ ਵਿੱਚ ਸੰਤੁਲਨ ਬਣਾਈ ਰੱਖਣ ਲਈ ਇੱਕ ਲਾਲ-ਕਾਲਾ ਰੁੱਖ ਰੀਲੋਰਿੰਗ ਅਤੇ ਪੁਨਰਗਠਨ ਦੀ ਵਰਤੋਂ ਕਰਦਾ ਹੈ.

ਤੁਸੀਂ ਦੇਖ ਸਕਦੇ ਹੋ ਕਿ ਆਰਬੀ ਦੇ ਦਰੱਖਤ ਕਿਵੇਂ ਆਪਣੇ ਆਪ ਨੂੰ ਮੁੜ ਸੰਗਠਿਤ ਕਰਦੇ ਹਨ ਅਤੇ ਪੁਨਰ ਗਠਨ ਕਰਦੇ ਹਨ ਇਥੇ.

ਮੁੜ ਰੰਗਤ

ਇਹ ਕੁਝ ਲਾਲ ਨੋਡਾਂ ਦੇ ਰੰਗ ਨੂੰ ਕਾਲੇ ਅਤੇ ਇਸਦੇ ਉਲਟ ਬਦਲਣ ਦਾ ਸੰਕੇਤ ਦਿੰਦਾ ਹੈ, ਇਹ ਉਦੋਂ ਵੀ ਕੀਤਾ ਜਾਂਦਾ ਹੈ ਜਦੋਂ ਲਾਲ ਨੋਡ ਦੇ ਲਾਲ ਮਾਪਿਆਂ ਦਾ ਭਰਾ ਲਾਲ ਹੁੰਦਾ ਹੈ.

ਲਾਲ-ਕਾਲੀ ਲੜੀ ਜਾਣ ਪਛਾਣ

 

ਪੁਨਰਗਠਨ

ਇਹ ਦਰੱਖਤ ਦੇ ਘੁੰਮਣ ਨੂੰ ਦਰਸਾਉਂਦਾ ਹੈ, ਇਹ ਉਦੋਂ ਵੀ ਕੀਤਾ ਜਾਂਦਾ ਹੈ ਜਦੋਂ ਲਾਲ ਬੱਚੇ ਦੇ ਲਾਲ ਮਾਪੇ ਅਤੇ ਕਾਲੇ ਜਾਂ ਨਲ ਚਾਚੇ ਹੁੰਦੇ ਹਨ. ਪੁਨਰਗਠਨ ਦੇ ਚਾਰ ਕੇਸ ਹਨ,

  • ਸੱਜੇ
  • ਖੱਬੇ
  • ਸਜਾ ਖਬਾ
  • ਖੱਬੇ ਸੱਜੇ

ਐਪਲੀਕੇਸ਼ਨ

  • ਸਵੈ-ਸੰਤੁਲਨ BSTs ਨੂੰ ਲਾਗੂ ਕਰਨ ਲਈ ਅਸਲ-ਸੰਸਾਰ ਦੀਆਂ ਲਾਇਬ੍ਰੇਰੀਆਂ ਵਿੱਚ ਵਰਤਿਆ ਜਾਂਦਾ ਹੈ.
  • ਦੇ ਤੌਰ ਤੇ ਵਰਤਿਆ ਗਿਆ ਟ੍ਰੀਸੈੱਟ ਅਤੇ ਜਾਵਾ ਵਿਚ ਟ੍ਰੀਮੈਪ ਅਤੇ ਸੀ ++ ਵਿਚ ਸੈੱਟ ਅਤੇ ਨਕਸ਼ੇ.

ਖੋਜ ਕਰਨਾ

ਇੱਕ ਲਾਲ-ਕਾਲਾ ਰੁੱਖ ਇੱਕ ਬੀਐਸਟੀ ਹੈ, ਇਸ ਲਈ ਆਰਬੀਟੀ ਵਿੱਚ ਖੋਜ ਕਰਨਾ ਬਿਲਕੁਲ ਉਸੇ ਤਰ੍ਹਾਂ ਹੈ ਜਿਵੇਂ ਕਿ ਬੀਐਸਟੀ ਵਿੱਚ ਖੋਜ ਕਰਨਾ, ਨੋਡ ਦਾ ਰੰਗ ਮਹੱਤਵ ਨਹੀਂ ਰੱਖਦਾ.