Оршил
Энэ нийтлэл нь хоёртын хайлтын модны тухай юм. Би саяхан нэг нийтлэл бичсэн Тэнд би хоёртын модыг нэг их анхаарч үзээгүй, учир нь хайх, оруулах, устгах аргууд нь хамааралгүй байсан. Одоо би модны тухай нийтлэл бичихээр шийдлээ. Эхэлцгээе.
Мод нь ирмэгээр холбогдсон зангилаанаас бүрдэх өгөгдлийн бүтэц юм. Мод бол графикийн онцгой тохиолдол гэж бид хэлж чадна. Энд жишээ мод байна:
Энэ бол хоёртын хайлтын мод биш юм! Бүх зүйл таслагдсан!
Нэр томъёо
Root буюу эх
Модны үндэс - энэ бол түүний хамгийн дээд цэг юм. Жишээн дээр энэ нь зангилаа А байна. Модны хувьд үндэсээс өөр ямар ч зангилаа руу зөвхөн нэг зам хүргэж болно! Үнэн хэрэгтээ аливаа зангилаа нь энэ зангилаанд тохирох дэд модны үндэс гэж үзэж болно.
Эцэг эх / үр удам
Үндэсээс бусад бүх зангилаа нь нөгөө зангилаа руу чиглэсэн яг нэг ирмэгтэй. Одоогийнхоос дээш байрлах зангилаа гэж нэрлэгддэг эцэг эх энэ зангилаа. Одоогийнхоос доогуур байрлах ба түүнтэй холбогдсон зангилаа гэж нэрлэгддэг үр удам энэ зангилаа. Нэг жишээ татъя. В зангилааг авъя, тэгвэл түүний эцэг эх нь А зангилаа, хүүхдүүд нь 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;
}
//...остальные методы узла
}
Зангилаа бүр хоёр хүүхэдтэй (lewChild ба/эсвэл 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 элемент байгаа бол энэ нь үндсэн 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 гэж тохируулбал энэ зангилаа нь үндэс болсон дэд модны талаарх мэдээллийг алдах болно. Модыг зайлуулах аргыг гурван тохиолдолд хуваадаг.
Эхний тохиолдол. Устгагдаж буй зангилаа хүүхэдгүй байна
Хэрэв устгаж буй зангилаа хүүхэдгүй бол энэ нь навч гэсэн үг юм. Тиймээс та түүний эцэг эхийн leftChild эсвэл rightChild талбаруудыг 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());
}
}
дүгнэлт
Эцэст нь! Хэрэв би юу ч тайлбарлаагүй эсвэл ямар нэгэн сэтгэгдэл байвал сэтгэгдэл дээр үлдээнэ үү. Амласан ёсоороо би бүрэн кодыг өгнө.
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
O(n) хүртэл доройтол
Та нарын ихэнх нь анзаарсан байх: Хэрэв та модыг тэнцвэргүй болговол яах вэ? Жишээ нь, мод дээр нэмэгдэж буй түлхүүрүүдтэй зангилаануудыг байрлуул: 1,2,3,4,5,6... Дараа нь мод нь зарим талаараа холбоотой жагсаалттай төстэй болно. Тийм ээ, мод нь модны бүтэц, улмаар өгөгдөлд нэвтрэх үр ашгийг алдах болно. Хайх, оруулах, устгах үйлдлүүдийн нарийн төвөгтэй байдал нь холбосон жагсаалтынхтай адил болно: O(n). Энэ бол миний бодлоор хоёртын модны сул талуудын нэг юм.
Зөвхөн бүртгэлтэй хэрэглэгчид санал асуулгад оролцох боломжтой. , гуйя.
Би төв дээр удаан ажиллаагүй бөгөөд ямар сэдвээр ямар нийтлэлүүдийг илүү их үзэхийг хүсч байгааг мэдмээр байна?
-
Өгөгдлийн бүтэц
-
Алгоритм (DP, рекурс, өгөгдөл шахах гэх мэт)
-
Өгөгдлийн бүтэц, алгоритмыг бодит амьдрал дээр ашиглах
-
Андройд програмуудыг Java хэл дээр програмчлах
-
Java хэл дээр вэб программчлал хийх
2 хэрэглэгч санал өгсөн. 1 хэрэглэгч түдгэлзсэн.
Эх сурвалж: www.habr.com