ቅድመ-ጥቅስ
ይህ ጽሑፍ ስለ ሁለትዮሽ ፍለጋ ዛፎች ነው. በቅርቡ ስለ አንድ ጽሑፍ ጽፌ ነበር። እዚያም ለሁለትዮሽ ዛፎች በትክክል ትኩረት አልሰጠሁም, ምክንያቱም የመፈለጊያ, የማስገባት እና የመሰረዝ ዘዴዎች ጠቃሚ አልነበሩም. አሁን ስለ ዛፎች አንድ ጽሑፍ ለመጻፍ ወሰንኩ. ምናልባት እንጀምራለን.
ዛፍ በጠርዝ የተገናኙ አንጓዎችን የያዘ የመረጃ መዋቅር ነው። አንድ ዛፍ የግራፍ ልዩ ጉዳይ ነው ማለት እንችላለን. አንድ ምሳሌ ዛፍ እነሆ:
ይህ ሁለትዮሽ ፍለጋ ዛፍ አይደለም! ሁሉም ነገር ከቁጥጥር በታች ነው!
ቃላት ትርጓሜ
ስርወ
የዛፍ ሥር ከፍተኛው መስቀለኛ መንገድ ነው. በምሳሌው ውስጥ ይህ መስቀለኛ መንገድ A ነው በዛፉ ውስጥ አንድ መንገድ ብቻ ከሥሩ ወደ ሌላ ማንኛውም መስቀለኛ መንገድ ሊመራ ይችላል! እንደ እውነቱ ከሆነ, ማንኛውም መስቀለኛ መንገድ ከዚህ መስቀለኛ መንገድ ጋር የሚዛመደው የንዑስ ዛፍ ሥር ተደርጎ ሊወሰድ ይችላል.
ወላጆች / ዘሮች
ከሥሩ በስተቀር ሁሉም አንጓዎች በትክክል አንድ ጠርዝ ወደ ሌላ መስቀለኛ መንገድ የሚወስድ ነው። አሁን ካለው መስቀለኛ መንገድ በላይ ያለው መስቀለኛ መንገድ ይባላል ወላጅ ይህ መስቀለኛ መንገድ. ከአሁኑ በታች የሚገኝ እና ከእሱ ጋር የተገናኘ መስቀለኛ መንገድ ይባላል ዘር ይህ መስቀለኛ መንገድ. አንድ ምሳሌ እንውሰድ። መስቀለኛ መንገድ B ይውሰዱ፣ ከዚያ ወላጁ መስቀለኛ መንገድ A ይሆናል፣ እና ልጆቹ አንጓዎች D፣ E እና F ይሆናሉ።
ሉህ
ልጆች የሌሉት መስቀለኛ መንገድ የዛፉ ቅጠል ይባላል. በምሳሌው ውስጥ አንጓዎች D, E, F, G, I, J, K ቅጠሎች ይሆናሉ.
ይህ መሰረታዊ የቃላት አነጋገር ነው። ሌሎች ጽንሰ-ሐሳቦች በኋላ ላይ ይብራራሉ. ስለዚህ, ሁለትዮሽ ዛፍ እያንዳንዱ መስቀለኛ መንገድ ከሁለት በላይ ልጆች የማይኖረውበት ዛፍ ነው. እንደገመቱት, ከምሳሌው ውስጥ ያለው ዛፍ ሁለትዮሽ አይሆንም, ምክንያቱም አንጓዎች B እና H ከሁለት በላይ ልጆች አሏቸው. የሁለትዮሽ ዛፍ ምሳሌ ይኸውና፡-
የዛፉ አንጓዎች ማንኛውንም መረጃ ሊይዝ ይችላል. ሁለትዮሽ የፍለጋ ዛፍ የሚከተሉትን ባህሪያት ያለው ሁለትዮሽ ዛፍ ነው.
- ሁለቱም ግራ እና ቀኝ የታች ዛፎች ሁለትዮሽ ፍለጋ ዛፎች ናቸው።
- ሁሉም የዘፈቀደ መስቀለኛ መንገድ X የግራ ንዑስ ኖዶች የውሂብ ቁልፍ እሴቶች ከራሱ መስቀለኛ X የውሂብ ቁልፍ እሴት ያነሱ ናቸው።
- ሁሉም የዘፈቀደ መስቀለኛ መንገድ X የቀኝ ንዑስ አንጓዎች ከራሱ የመስቀለኛ መንገድ X የውሂብ ቁልፍ እሴት የበለጠ ወይም እኩል የሆነ የውሂብ ቁልፍ እሴቶች አሏቸው።
ቁልፍ - የመስቀለኛ ክፍል አንዳንድ ባህሪዎች (ለምሳሌ ፣ ቁጥር)። ይህ ቁልፍ የሚዛመደውን የዛፉን አካል ለማግኘት ቁልፉ ያስፈልጋል። የሁለትዮሽ ፍለጋ ዛፍ ምሳሌ:
የዛፍ እይታ
እየሄድኩ ስሄድ ግንዛቤህን ለማሻሻል አንዳንድ (ምናልባት ያልተሟሉ) የኮድ ቁራጮችን አካትቻለሁ። ሙሉው ኮድ በአንቀጹ መጨረሻ ላይ ይሆናል።
ዛፉ በመስቀለኛ መንገድ የተሠራ ነው. የመስቀለኛ ክፍል መዋቅር;
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
//...остальные методы узла
}
እያንዳንዱ መስቀለኛ መንገድ ሁለት ልጆች አሉት (የግራ ልጅ እና/ወይም የቀኝ ልጅ ልጆች ባዶ ሊሆኑ ይችላሉ)። ምናልባት በዚህ ሁኔታ ውስጥ የቁጥር ውሂብ በመስቀለኛ መንገድ ውስጥ የተከማቸ ውሂብ መሆኑን ተረድተህ ይሆናል; ቁልፍ - የመስቀለኛ መንገድ ቁልፍ.
ቋጠሮውን አውቀናል, አሁን ስለ ዛፎች አስቸኳይ ችግሮች እንነጋገር. እዚህ እና ከታች, "ዛፍ" የሚለው ቃል የሁለትዮሽ ፍለጋ ዛፍ ጽንሰ-ሐሳብ ማለት ነው. የሁለትዮሽ ዛፍ አወቃቀር;
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
እንደ ክፍል መስክ እኛ የምንፈልገው የዛፉን ሥር ብቻ ነው, ምክንያቱም ከሥሩ, የ getLeftChild () እና GetRightChild () ዘዴዎችን በመጠቀም ወደ ማንኛውም የዛፉ መስቀለኛ መንገድ መድረስ ይችላሉ.
የዛፍ አልጎሪዝም
Поиск
የተሰራ ዛፍ አለህ እንበል። በቁልፍ ቁልፍ ኤለመንት እንዴት ማግኘት ይቻላል? በቅደም ተከተል ከዛፉ ስር ስር መንቀሳቀስ እና የቁልፉን እሴት ከሚቀጥለው መስቀለኛ መንገድ ቁልፍ ጋር ማወዳደር ያስፈልግዎታል-ቁልፉ ከሚቀጥለው መስቀለኛ መንገድ ቁልፍ ያነሰ ከሆነ ከዚያ ወደ የመስቀለኛ ግራው ዘር ይሂዱ ፣ የበለጠ ከሆነ - በቀኝ በኩል, ቁልፎቹ እኩል ከሆኑ - የሚፈለገው መስቀለኛ መንገድ ተገኝቷል! ተዛማጅ ኮድ፡
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
የአሁኑ ጊዜ ከንቱ ከሆነ፣ ድግግሞሹ የዛፉ ጫፍ ላይ ደርሷል (በጽንሰ-ሀሳብ ደረጃ በዛፉ ውስጥ በሌለው ቦታ ላይ ነዎት - የቅጠል ልጅ)።
በተመጣጣኝ ዛፍ ላይ የፍለጋ አልጎሪዝምን ውጤታማነት አስቡ (አንጓዎች ብዙ ወይም ያነሰ በእኩል የሚከፋፈሉበት ዛፍ)። ከዚያ የፍለጋው ውጤታማነት O(log(n))፣ እና መሰረቱ 2 ሎጋሪዝም ይሆናል፡ ይመልከቱ፡ በተመጣጣኝ ዛፍ ውስጥ n ኤለመንቶች ካሉ ይህ ማለት ሎግ(n) መሰረት 2 የዛፉ ደረጃዎች ይኖራሉ ማለት ነው። እና በፍለጋ ውስጥ, ለአንድ ዑደት አንድ ደረጃ, ወደ አንድ ደረጃ ይወርዳሉ.
አገባ
የፍለጋውን ፍሬ ነገር ከተረዳህ፣ ማስገባትህን ለመረዳት አስቸጋሪ አይሆንም። ወደ ዛፉ ቅጠል (በፍለጋው ውስጥ በተገለጹት የትውልድ ህጎች መሰረት) መውረድ እና የእሱ ዘር መሆን ያስፈልግዎታል - በግራ ወይም በቀኝ ፣ እንደ ቁልፉ። ትግበራ፡
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
በዚህ ሁኔታ, አሁን ካለው መስቀለኛ መንገድ በተጨማሪ, ስለ የአሁኑ መስቀለኛ ወላጅ መረጃ ማከማቸት አስፈላጊ ነው. የአሁኑ ጊዜ ባዶ በሚሆንበት ጊዜ፣ የወላጅ ተለዋዋጭ የምንፈልገውን ሉህ ይይዛል።
የማስገቢያ ቅልጥፍና ከፍለጋው ጋር ተመሳሳይ ይሆናል - O(log(n))።
ሰርዝ
መሰረዝ በዛፍ መከናወን ያለበት በጣም ውስብስብ ቀዶ ጥገና ነው. በመጀመሪያ እኛ የምናስወግድበትን ኤለመንት መፈለግ አስፈላጊ እንደሚሆን ግልጽ ነው. ግን ከዚያ ምን? ማጣቀሻውን ወደ ባዶነት ብቻ ካስቀመጥነው ይህ መስቀለኛ መንገድ ስለሆነው ንዑስ ዛፍ መረጃ እናጣለን። የዛፍ ማስወገጃ ዘዴዎች በሦስት ሁኔታዎች ይከፈላሉ.
የመጀመሪያ ጉዳይ። የሚወገደው መስቀለኛ መንገድ ልጆች የሉትም።
የሚሰረዘው መስቀለኛ መንገድ ልጆች ከሌሉት, ይህ ማለት ቅጠል ነው ማለት ነው. ስለዚህ፣ የወላጁን የግራ ልጅ ወይም የቀኝ ልጅ መስኮችን በቀላሉ ባዶ ማድረግ ይችላሉ።
ሁለተኛ ጉዳይ። የሚወገደው መስቀለኛ መንገድ አንድ ልጅ አለው
ይህ ጉዳይም በጣም አስቸጋሪ አይደለም. ወደ ምሳሌአችን እንመለስ። አንድ ኤለመንት ከቁልፍ 14 ጋር መሰረዝ አለብን እንበል። 10 ቁልፍ ያለው የመስቀለኛ ክፍል ትክክለኛው ልጅ ስለሆነ፣ ማንኛውም ዘሮቹ (በዚህ ሁኔታ ትክክለኛው) ከ 10 በላይ የሆነ ቁልፍ እንደሚኖራቸው ይስማሙ። በቀላሉ ከዛፉ ላይ "መቁረጥ" ይችላል, እና ወላጁን በቀጥታ ከተሰረዘ የመስቀለኛ መንገድ ልጅ ጋር ያገናኛል, ማለትም. መስቀለኛ መንገድን ከቁልፍ 10 ወደ መስቀለኛ መንገድ 13 ያገናኙ። የወላጁ የግራ ልጅ የሆነውን መስቀለኛ መንገድ መሰረዝ ካለብን ሁኔታው ተመሳሳይ ይሆናል። ለራስህ አስብ - ትክክለኛ ተመሳሳይነት.
ሦስተኛው ጉዳይ. መስቀለኛ መንገድ ሁለት ልጆች አሉት
በጣም አስቸጋሪው ጉዳይ. አዲስ ምሳሌ እንመልከት።
ተተኪን ፈልግ
መስቀለኛ መንገድን በቁልፍ ማስወገድ አለብን እንበል 25. ማንን በእሱ ቦታ እናስቀምጠው? ከተከታዮቹ አንዱ (የዘር ዘሮች ወይም ዘሮች) መሆን አለበት። ተተኪ(የተወገደውን መስቀለኛ ቦታ የሚወስደው).
ተተኪው ማን መሆን እንዳለበት እንዴት ያውቃሉ? በማስተዋል፣ ይህ በዛፉ ውስጥ ያለው መስቀለኛ መንገድ ሲሆን ቁልፉ ከተወገደው የሚቀጥለው ትልቁ ነው። ስልተ ቀመር እንደሚከተለው ነው. ወደ ቀኝ ልጁ መሄድ ያስፈልግዎታል (ሁልጊዜ ወደ ቀኝ ነው ፣ ምክንያቱም የተተኪው ቁልፍ ከመሰረዙ መስቀለኛ መንገድ የበለጠ ነው ተብሎ ስለሚነገር) እና ከዚያ በዚህ የቀኝ ግራ ልጆች ሰንሰለት ውስጥ ይሂዱ። ልጅ ። ምሳሌ ውስጥ, እኛ ቁልፍ 35 ጋር መስቀለኛ መንገድ መሄድ አለብን, ከዚያም በውስጡ ግራ ልጆች ሰንሰለት ወደ ቅጠል ወደ ታች መሄድ አለብን - በዚህ ሁኔታ ውስጥ, ይህ ሰንሰለት ቁልፍ 30. ጋር ብቻ መስቀለኛ ያቀፈ ነው, እኛ እየፈለግን ነው. ከተፈለገው መስቀለኛ መንገድ የሚበልጠው በኖዶች ስብስብ ውስጥ ያለው ትንሹ መስቀለኛ መንገድ.
ተተኪ የፍለጋ ዘዴ ኮድ፡-
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;//родитель преемника
Node<T> successor = deleteNode;//преемник
Node<T> current = successor.getRightChild();//просто "пробегающий" узел
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
//на выходе из цикла имеем преемника и родителя преемника
if (successor != deleteNode.getRightChild()) {//если преемник не совпадает с правым потомком удаляемого узла
parentSuccessor.setLeftChild(successor.getRightChild());//то его родитель забирает себе потомка преемника, чтобы не потерять его
successor.setRightChild(deleteNode.getRightChild());//связываем преемника с правым потомком удаляемого узла
}
return successor;
}
የመሰረዝ ዘዴው ሙሉ ኮድ፡-
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;//В зависимости от того, является ли удаляемый узел левым или правым потомком своего родителя, булевская переменная isLeftChild будет принимать значение true или false соответственно.
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {//первый случай
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {//второй случай
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {//третий случай
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
ውስብስብነቱ ወደ O(log(n)) ሊጠጋ ይችላል።
በዛፍ ውስጥ ከፍተኛውን / ዝቅተኛውን ማግኘት
በግልጽ ለማየት እንደሚቻለው በዛፉ ውስጥ ዝቅተኛውን / ከፍተኛውን እሴት እንዴት ማግኘት እንደሚቻል - የዛፉን የግራ / የቀኝ ንጥረ ነገሮች ሰንሰለት በቅደም ተከተል ማለፍ ያስፈልግዎታል; ቅጠሉ ላይ ሲደርሱ ዝቅተኛው/ከፍተኛው አካል ይሆናል።
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
ውስብስብነት - ኦ (ሎግ(n))
ሲሜትሪክ ማለፊያ
መሻገሪያ ማለት አንድ ነገር ለማድረግ ወደ እያንዳንዱ የዛፉ መስቀለኛ መንገድ መጎብኘት ነው.
ተደጋጋሚ ሲሜትሪክ መሻገሪያ ስልተ ቀመር፡
- በግራ ልጅ ላይ እርምጃ ይውሰዱ
- ከራስህ ጋር እርምጃ ውሰድ
- በትክክለኛው ልጅ ላይ እርምጃ ይውሰዱ
ኮድ:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
መደምደሚያ
በመጨረሻ! የሆነ ነገር ካላብራራሁ ወይም ምንም አስተያየት ከሌለኝ በአስተያየቶቹ ውስጥ እየጠበቅኩ ነው. ቃል በገባነው መሰረት ሙሉ ኮድ እዚህ አለ።
Node.java፡
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public void setLeftChild(Node<T> newNode) {
leftChild = newNode;
}
public void setRightChild(Node<T> newNode) {
rightChild = newNode;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
public T getData() {
return data;
}
public int getKey() {
return key;
}
}
BinaryTree.java፡
public class BinaryTree<T> {
private Node<T> root;
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;
Node<T> successor = deleteNode;
Node<T> current = successor.getRightChild();
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
if (successor != deleteNode.getRightChild()) {
parentSuccessor.setLeftChild(successor.getRightChild());
successor.setRightChild(deleteNode.getRightChild());
}
return successor;
}
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");
inOrder(current.getRightChild());
}
}
}
PS
ወደ ኦ(n) መበላሸት
ብዙዎቻችሁ አስተውላችሁ ይሆናል፡ ዛፉ ሚዛናዊ እንዳይሆን ብታደርጉትስ? ለምሳሌ በዛፉ ውስጥ የሚጨምሩ ቁልፎችን ያኑሩ: 1,2,3,4,5,6... ከዛ ዛፉ በተወሰነ መልኩ የተያያዘ ዝርዝርን ያስታውሳል. እና አዎ, ዛፉ የዛፉን መዋቅር ያጣል, እና ስለዚህ የውሂብ ተደራሽነት ውጤታማነት. የፍለጋ፣ የማስገቢያ እና የስረዛ ስራዎች ውስብስብነት ከተገናኘው ዝርዝር፡ ኦ(n) ጋር ተመሳሳይ ይሆናል። ይህ በጣም አስፈላጊ ከሆኑት አንዱ ነው, በእኔ አስተያየት, የሁለትዮሽ ዛፎች ጉዳቶች.
በዳሰሳ ጥናቱ ውስጥ የተመዘገቡ ተጠቃሚዎች ብቻ መሳተፍ ይችላሉ። እባክህን።
በሐበሬ ላይ ለረጅም ጊዜ አልቆይም ፣ እና በየትኞቹ ርዕሶች ላይ የትኞቹን መጣጥፎች የበለጠ ማየት ይፈልጋሉ?
-
የውሂብ መዋቅሮች
-
አልጎሪዝም (DP፣ ተደጋጋሚነት፣ የውሂብ መጭመቅ፣ ወዘተ)
-
በእውነተኛ ህይወት ውስጥ የውሂብ አወቃቀሮች እና ስልተ ቀመሮች አተገባበር
-
አንድሮይድ መተግበሪያዎችን በጃቫ ማሰናዳት
-
ጃቫ የድር መተግበሪያ ፕሮግራሚንግ
2 ተጠቃሚዎች ድምጽ ሰጥተዋል። 1 ተጠቃሚ ተቆጥቧል።
ምንጭ፡ www.habr.com