وړاندې کول
دا مقاله د بائنری لټون ونو په اړه ده. ما پدې وروستیو کې یوه مقاله لیکلې وه هلته ما په حقیقت کې بائنری ونو ته پام نه دی کړی، ځکه چې د لټون کولو، داخلولو، حذف کولو طریقې اړونده نه وې. اوس ما پریکړه وکړه چې د ونو په اړه یوه مقاله ولیکم. شاید موږ به پیل وکړو.
ونې د ډیټا جوړښت دی چې د څنډو په واسطه تړل شوي نوډونه لري. موږ کولی شو ووایو چې ونه د ګراف یوه ځانګړې قضیه ده. دلته د ونې مثال دی:
دا د بائنری لټون ونې نه ده! هرڅه د کټ لاندې دي!
اصطلاحات
روټ
د ونې ريښه تر ټولو لوړ نوډ دی. په مثال کې، دا نوډ A دی. په ونه کې، یوازې یوه لاره کولی شي له ریښې څخه بل نوډ ته لاړ شي! په حقیقت کې، هر نوډ د دې نوډ پورې اړوند د فرعي ونې ریښې په توګه ګڼل کیدی شي.
مور او پلار / اولادونه
د ريښي پرته ټول نوډونه په سمه توګه يوه څنډه لري چې بل نوډ ته ځي. د اوسني نوډ څخه پورته نوډ ویل کیږي مور او پلار دا نوډ. یو نوډ چې د اوسني یو لاندې موقعیت لري او له هغې سره وصل دی ویل کیږي نسل دا نوډ. راځئ چې یو مثال واخلو. نوډ B واخلئ، نو د هغې مور او پلار به نوډ A وي، او ماشومان به یې نوډ D، E، F وي.
لیف
هغه نوډ چې هیڅ اولاد نلري د ونې پاڼی بلل کیږي. په مثال کې، نوډونه D، E، F، G، I، J، K به پاڼي وي.
دا اساسي اصطلاحات دي. نور مفکورې به وروسته بحث شي. نو، د بائنری ونې یوه ونه ده چې په هر نوډ کې به له دوو څخه زیات ماشومان ونه لري. لکه څنګه چې تاسو اټکل کړی، د مثال څخه ونه به بائنری نه وي، ځکه چې نوډونه B او H له دوو څخه زیات ماشومان لري. دلته د بائنری ونې یوه بیلګه ده:
د ونې نوډونه کولی شي هر ډول معلومات ولري. د بائنری لټون ونې یوه بائنری ونه ده چې لاندې ځانګړتیاوې لري:
- دواړه کیڼ او ښي فرعي ونې د بائنری لټون ونې دي.
- د خپل سري نوډ 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 logarithm وي. وګورئ: که چیرې په متوازن ونې کې n عناصر شتون ولري، نو دا پدې مانا ده چې د ونې اساس 2 درجې به log(n) وي. او په لټون کې، د دورې د یوې مرحلې لپاره، تاسو یو سطح ته لاړ شئ.
وليکی
که تاسو د لټون جوهر درک کړی وي، نو دا به ستاسو لپاره ستونزمن نه وي چې د ننوتلو په اړه پوه شي. تاسو یوازې اړتیا لرئ د ونې پاڼي ته لاړ شئ (د نزول د قواعدو سره سم چې په لټون کې تشریح شوي) او د هغې نسل شئ - کیڼ یا ښیې، د کیلي پورې اړه لري. تطبیق:
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)).
ړنګول
حذف کول خورا پیچلي عملیات دي چې د ونې سره باید ترسره شي. دا روښانه ده چې لومړی به اړین وي چې هغه عنصر ومومئ چې موږ یې لرې کوو. خو بیا څه؟ که موږ په ساده ډول د هغې حواله null ته وټاکو، نو موږ به د فرعي ونې په اړه معلومات له لاسه ورکړو چې ریښه یې دا نوډ ده. د ونې د لرې کولو میتودونه په دریو قضیو ویشل شوي دي.
لومړۍ قضیه. هغه نوډ چې له مینځه وړل کیږي هیڅ اولاد نلري.
که هغه نوډ چې له مینځه وړل کیږي هیڅ ماشومان نلري، دا پدې مانا ده چې دا یوه پاڼه ده. له همدې امله، تاسو کولی شئ په ساده ډول د دې د مور او پلار د بائیں ماشوم یا د حق ماشوم ساحې null ته تنظیم کړئ.
دویمه قضیه. هغه نوډ چې لیرې کیږي یو ماشوم لري
دا قضیه هم ډیره ستونزمنه نه ده. راځئ چې بیرته زموږ مثال ته لاړ شو. فرض کړئ چې موږ د کیلي 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;
}
پیچلتیا - O(log(n))
سیمالټ بای پاس
ټراورسل د ونې هر نوډ ته لیدنه ده ترڅو د هغې سره یو څه وکړي.
تکراري سمیټریک ټراورسل الګوریتم:
- په چپ ماشوم باندې عمل وکړئ
- له ځان سره یو عمل وکړئ
- په سم ماشوم باندې عمل وکړئ
کوډ:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
پایلې
په پای کې! که زه یو څه تشریح نه کړم یا کوم نظر لرم، نو زه په تبصرو کې انتظار کوم. لکه څنګه چې ژمنه شوې، دلته بشپړ کوډ دی.
نوډ جاوا:
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
O(n) ته انحطاط
ستاسو څخه ډیری شاید لیدلي وي: که تاسو ونه غیر متوازنه کړئ نو څه به وکړئ؟ د مثال په توګه، په ونې کې د زیاتیدونکي کیلي سره نوډونه واچوئ: 1,2,3,4,5,6... بیا به ونه یو څه د تړل شوي لیست یادونه وکړي. او هو، ونه به خپل د ونې جوړښت له لاسه ورکړي، او له همدې امله د معلوماتو لاسرسي موثریت. د لټون، داخلولو، او حذف کولو عملیاتو پیچلتیا به د تړل شوي لیست په څیر وي: O(n). دا یو له خورا مهم څخه دی، زما په نظر، د بائنری ونو زیانونه.
یوازې راجستر شوي کاروونکي کولی شي په سروې کې برخه واخلي. مهرباني وکړئ
زه د ډیرې مودې لپاره په هابري کې نه یم، او زه غواړم پوه شم چې په کومو موضوعاتو کې کوم مقالې غواړئ چې تاسو نور وګورئ؟
-
د معلوماتو جوړښتونه
-
الګوریتمونه (DP، تکرار، د معلوماتو کمپریشن، او نور)
-
په ریښتیني ژوند کې د ډیټا جوړښتونو او الګوریتمونو پلي کول
-
په جاوا کې د Android غوښتنلیکونو پروګرام کول
-
د جاوا ویب غوښتنلیک پروګرام کول
2 کاروونکو رایه ورکړه. 1 کارن پاتې شو.
سرچینه: www.habr.com